/* 最大密集子图子图裸题 解法:设源点s和汇点t 根据胡波涛的<最小割模型在信息学中的应用> s-每个点,权值为原边权和m, 每个点-t,权值为m+2*g-degree[i], 原来的边u-v ,权值为原权值 最小割f; flow=m*n-f; 二分g得到flow 逼近0; */ #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<queue> using namespace std; #define eps 1e-6 #define inf 0x3fffffff #define N 110 #define NN 1100 struct node { int u,v,next; double w; }bian[NN*8],f[NN]; int yong,head[N],dis[N],work[N]; void init() { yong=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,double w) { bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } int degree[N]; void build(int m,double mid,int n) { int i; init(); for(i=1;i<=n;i++) { addedge(0,i,m); addedge(i,0,0); addedge(i,n+1,1.0*m+2*mid-degree[i]); addedge(n+1,i,0); } for(i=1;i<=m;i++) { addedge(f[i].u,f[i].v,1); addedge(f[i].v,f[i].u,1); } return ; } int bfs(int S,int T) { queue<int>q; memset(dis,-1,sizeof(dis)); dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w>0&&dis[v]==-1) { dis[v]=dis[u]+1; if(v==T) return 1; q.push(v); } } } return 0; } double dfs(int S,double a,int T) { if(S==T)return a; for(int &i=work[S];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w>0&&dis[v]==dis[S]+1) { double tt=dfs(v,min(a,bian[i].w),T); if(tt>0) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } double dinic(int S,int T) { double ans=0; while(bfs(S,T)) { memcpy(work,head,sizeof(head)); while(1) { double tt=dfs(S,inf,T);//割出来的可能是负值 if(tt<eps)break; ans+=tt; } } return ans; } int vis[N],ans[N],len; void dfs1(int u) { int i; vis[u]=1; for(i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(!vis[v]&&bian[i].w>0) { ans[++len]=v; dfs1(v); } } return ; } int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } int main() { int n,m,i,s,t,dd; double st,en,mid,flow; while(scanf("%d%d",&n,&m)!=EOF) { if(!m) { printf("1 1 "); continue; } memset(degree,0,sizeof(degree)); for(i=1;i<=m;i++) { scanf("%d%d",&f[i].u,&f[i].v); degree[f[i].u]++; degree[f[i].v]++; } s=0;t=n+1; st=0;en=m;//dd=0; while(en-st>1.0/n/n) { mid=(st+en)/2; // printf("%.2f ",mid); // dd++; // if(dd==12)break; build(m,mid,n); flow=dinic(s,t); // printf("%.2f ",flow); flow=1.0*m*n-flow; if(flow>eps) st=mid; else en=mid; } init(); build(m,st,n); dinic(s,t); memset(vis,0,sizeof(vis)); len=0; dfs1(s); qsort(ans+1,len,sizeof(ans[0]),cmp); printf("%d ",len); for(i=1;i<=len;i++) printf("%d ",ans[i]); } return 0;}