记录编号	95144	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NERRC 2006][POJ3155]生活的艰辛	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2014-04-04 11:06:29	内存使用	0.34 MiB

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;

const int MAXN=100+10;
const int MAXM=1000+10;

const int MAXP=2*MAXN+MAXM;

const int INF=10000*10000;
const int bei=1000;
int N,M;
struct edge{
	int from,to,cap,flow;
};

struct dinic{
	int n,m,s,t;
	int cur[MAXP],d[MAXP];
	vector<int> G[MAXP];
	vector<edge> edges;
	bool inq[MAXP];
	
	void init(int s,int t){
		this->s=s;this->t=t;
		for(int i=0;i<MAXP;i++)G[i].clear();
		edges.clear();
	}
	
	void add_edge(int from,int to,int cap){
		//printf("from:%d to:%d cap:%d\n",from,to,cap);
		edges.push_back((edge){from,to,cap,0});
		edges.push_back((edge){to,from,0,0});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool BFS(){
		memset(d,0,sizeof(d));
		memset(inq,0,sizeof(inq));
		queue<int> q;
		q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]==0 && e.to!=s){
					d[e.to]=d[u]+1;
					if(!inq[e.to]){
						inq[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
		return d[t];
	}
	
	int DFS(int u,int a){
		if(u==t || a==0)return a;
		int flow=0;
		for(int &i=cur[u];i<G[u].size();i++){
			edge &e=edges[G[u][i]];
			if(d[e.to]!=d[u]+1)continue;
			int f=DFS(e.to,min(a,e.cap-e.flow));
			//if(f==0) return flow;
			a-=f;
			flow+=f;
			edge &ee=edges[G[u][i]^1];
			e.flow+=f;
			ee.flow-=f;
			if(a==0)return flow;
		}
		return flow;
	}
	
	void test(){
		for(int i=0;i<edges.size();i++){
			edge &e=edges[i];
			printf("from:%d to:%d cap:%d flow:%d\n",e.from,e.to,e.cap,e.flow);
		}
		for(int i=0;i<=t;i++){
			printf("d[%d]:%d\n",i,d[i]);
		}
		printf("======================\n");
	}
	
	int max_flow(){
		int flow=0;
		while(BFS()){
			//test();
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
	//	test();
		return flow;
	}
	
	bool vis[MAXP];
	void out_ans(){
		memset(vis,0,sizeof(vis));
		queue<int> q;
		q.push(s);vis[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();
			vis[u]=true;
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(e.cap>e.flow && !vis[e.to]){
					vis[e.to]=true;
					q.push(e.to);
				}
			}
		}
		
		int g_n=0;
		for(int i=1;i<=N;i++){
			if(vis[i])g_n++;
		}
		printf("%d\n",g_n);
		for(int i=1;i<=N;i++){
			if(vis[i])printf("%d\n",i);
		}
	}
	
}solver;



struct input{
	int a,b;
}inputs[MAXM];

void read(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++){
		input &in=inputs[i];
		scanf("%d %d",&in.a,&in.b);
	}
}

int test(int r){
	int s=0,t=N+M+1;
	int ans=0;
	solver.init(s,t);
	for(int i=1;i<=N;i++){
		solver.add_edge(i,t,r);
	}
	for(int i=1;i<=M;i++){
		int u=i+N;
		input &in=inputs[i];
		solver.add_edge(s,u,bei);
		ans+=bei;
		solver.add_edge(u,in.a,INF);
		solver.add_edge(u,in.b,INF);
	}
	ans=ans-solver.max_flow();
	if(ans==0)ans=-1;
	return ans;
}

void work(){
	read();
	if(M==0){
		printf("1\n1");
		return ;
	}
	int left=1,right=100*bei;
	while(right-left>=1){
		int mid=(right+left)/2;
		int tt=test(mid);
		if(tt>0){
			left=mid+1;
		}else if(tt<0){
			right=mid;
		}else{
			break;
		}
	}
	test(left-1);
	solver.out_ans();
}

void open(){
	//freopen("in.txt","r",stdin);
	freopen("hardlife.in","r",stdin);
	freopen("hardlife.out","w",stdout);
}

int main(){
	open();
	work();
	return 0;
}