题意：给出一副连通图，求出一个子图令g=sigma(E)/sigma(V);

h[g]=sigma(E)-g*sigma(V)；设G是最优值

则当h[g]>0:g<G

h[g]<0,g>G;

h[g]=0：g=G；

h[g]=(U*n-Cut[S,T])/2;

当最小割Cut[S,T]最小时，h[g]最大

分析：建图方式：对于<u,v>,建立正向边和反向边容量为1

对于每个点u建立s->u容量为U，建立u->t容量为U+2*g-du(du是每个点的度)

公式推导详见：最小割模型在信息学竞赛中的应用

当h[g]>eps时增大g，否则减小g，知道h[g]=eps

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"algorithm"

#include"math.h"

#include"vector"

#include"queue"

#define M 222

#define inf 0x3f3f3f3f

#define eps 1e-7

#define pps 1e-18

#define PI acos(-1.0)

using namespace std;

struct node

{

    int u,v,next;

    double w;

}edge[10009],e[1009];

int t,head[M],dis[M],degree[M],s[M],cnt,vis[M];

int cmp(int a,int b)

{

    return a<b;

}

double min(double a,double b)

{

    return a<b?a:b;

}

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v,double w,double fw)

{

    edge[t].u=u;

    edge[t].v=v;

    edge[t].w=w;

    edge[t].next=head[u];

    head[u]=t++;

    edge[t].u=v;

    edge[t].v=u;

    edge[t].w=fw;

    edge[t].next=head[v];

    head[v]=t++;

}

int bfs(int S,int T)

{

    queue<int>q;

    memset(dis,-1,sizeof(dis));

    q.push(S);

    dis[S]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].v;

            if(edge[i].w>pps&&dis[v]==-1)

            {

                dis[v]=dis[u]+1;

                if(v==T)

                    return 1;

                q.push(v);

            }

        }

    }

    return 0;

}

double dfs(int cur,double a,int T)

{

    if(cur==T)return a;

    for(int i=head[cur];~i;i=edge[i].next)

    {

        int v=edge[i].v;

        if(edge[i].w>pps&&dis[v]==dis[cur]+1)

        {

            double tt=dfs(v,min(a,edge[i].w),T);

            if(tt)

            {

                edge[i].w-=tt;

                edge[i^1].w+=tt;

                return tt;

            }

        }

    }

    return 0;

}

double Dinic(int S,int T)

{

    double ans=0;

    while(bfs(S,T))

    {

        while(double tt=dfs(S,inf,T))

            ans+=tt;

    }

    return ans;

}

void Creat(int n,int m,double g)

{

    init();

    int i;

    for(i=1;i<=m;i++)

        add(e[i].u,e[i].v,1,1);

    for(i=1;i<=n;i++)

    {

        add(0,i,m*1.0,0);

        add(i,n+1,m+2*g-degree[i],0);

    }

}

void dfs1(int u)

{

    vis[u]=1;

    s[cnt++]=u;

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v=edge[i].v;

        if(edge[i].w&&!vis[v])

            dfs1(v);

    }

}

int main()

{

    int n,m,i;

    while(scanf("%d%d",&n,&m)!=-1)

    {

        if(m==0)

        {

            printf("1\n1\n");

            continue;

        }

        memset(degree,0,sizeof(degree));

        for(i=1;i<=m;i++)

        {

            scanf("%d%d",&e[i].u,&e[i].v);

            degree[e[i].u]++;

            degree[e[i].v]++;

        }

        double l=1.0/n,r=m*1.0,mid,g;

        while(r-l>1.0/n/n)//论文以证明误差精度不会超过1/n/n

        {

            mid=(l+r)/2;

            Creat(n,m,mid);//重新构图

            double temp=(m*n*1.0-Dinic(0,n+1))/2.0;

            if(temp>eps)

            {

                l=mid;

                g=mid;

            }

            else r=mid;

        }

        Creat(n,m,g);//重新跑一边最大流，二分中最后一次跑的不应定是最优解

        Dinic(0,n+1);

        memset(vis,0,sizeof(vis));

        cnt=0;

        dfs1(0);

        sort(s,s+cnt,cmp);

        printf("%d\n",cnt-1);

        for(i=1;i<cnt;i++)

            printf("%d\n",s[i]);

    }

}