记录编号	380382	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NERRC 2006][POJ3155]生活的艰辛	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2017-03-09 08:11:13	内存使用	0.31 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define Pmax 150
#define Mmax 1010
#define eps 1e-7
#define hv(n) (fabs(n) < eps ? false : true)
vector<int> gp[Pmax];
vector<int> gto;
vector<double> cap;
int S, T;
int egu;
void adeg(int a, int b) {
	gp[a].push_back(egu++);
	gto.push_back(b);
	cap.push_back(0);

	gp[b].push_back(egu++);
	gto.push_back(a);
	cap.push_back(0);
}
int deep[Pmax];
int cur[Pmax];
bool BFS() {
	memset(deep, 0, sizeof(deep));
	memset(cur, 0, sizeof(cur));
	queue<int> ls;
	ls.push(S);
	deep[S] = 1;
	int x, t, v;
	while (!ls.empty()) {
		x = ls.front();
		ls.pop();
		if (x == T)
			break;
		for (int i = 0; i < (int)gp[x].size(); i++) {
			t = gp[x][i];
			v = gto[t];
			if (!deep[v] && hv(cap[t])) {
				deep[v] = deep[x]+1;
				ls.push(v);
			}
		}
	}
	return deep[T];
}
double DFS(int x, double mx) {
	if (x == T)
		return mx;
	int t, v;
	double fl = 0, dt;
	for (int &i = cur[x]; i < (int)gp[x].size(); i++) {
		t = gp[x][i];
		v = gto[t];
		if (deep[v] == deep[x]+1 && hv(cap[t])) {
			dt = DFS(v, min(cap[t], mx));
			mx -= dt;
			fl += dt;
			cap[t] -= dt;
			cap[t^1] += dt;
			if (!hv(mx))
				break;
		}
	}
	return fl;
}
/*
void pf() {
	for (int i = 0; i*2 < (int)cap.size(); i++) {
		printf("%d %d %lf %lf\n", gto[i<<1^1], gto[i<<1], cap[i<<1], cap[i<<1^1]);
	}
	printf("****\n");
}*/
double dinic() {
	double ans = 0;
	//printf("\n");
	//pf();
	while (BFS()) {
		ans += DFS(S, 1e12);
	//	pf();
	}
	return ans;
}
int N, M;
void init() {
	scanf("%d %d", &N, &M);
	S = 0;
	T = N+1;
	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		adeg(a, b);
		adeg(b, a);
	}
	for (int i = 1; i <= N; i++) {
		adeg(S, i);
		adeg(i, T);
	}
}
double U = Mmax;
void mkgp(double md) {
	for (int i = 0; i < M; i++) {
		cap[i<<2] = 1;
		cap[i<<2^1] = 0;
		cap[i<<2^2] = 1;
		cap[i<<2^3] = 0;
	}
	for (int i = M; i < M+N; i++) {
		cap[i<<2] = U;
		cap[i<<2^1] = 0;
		cap[i<<2^2] = U+2*md-(gp[i-M+1].size()-2)/2;
		cap[i<<2^3] = 0;
	}
}
bool ck(double md) {
	mkgp(md);
	double ans;
	ans = dinic();
	ans -= N*U;
	ans = -ans;
	if (ans > eps) {
		return false;
	}
	else
		return true;
}
void rBFS() {
	memset(deep, 0, sizeof(deep));
	queue<int> ls;
	ls.push(T);
	deep[T] = 1;
	int x, t, v;
	while (!ls.empty()) {
		x = ls.front();
		ls.pop();
		for (int i = 0; i < (int)gp[x].size(); i++) {
			t = gp[x][i];
			v = gto[t];
			if (!deep[v] && hv(cap[t^1])) {
				deep[v] = 1;
				ls.push(v);
			}
		}
	}
}
void ansit() {
	int ans = 0;
	for (int i = 1; i <= N; i++)
		if (deep[i])
			ans++;
	/*
	if (ans == 0) {
		rBFS();
		for (int i = 1; i <= N; i++)
			ans++;
		if (ans == 0)
			printf("1\n1\n");
		else {
			for (int )
		}
	}*/
	if (ans == 0)
		printf("1\n1\n");
	else {
		printf("%d\n", ans);
		for (int i = 1; i <= N; i++) {
			if (deep[i])
				printf("%d\n", i);
		}
	}
}
void work() {
	double l = 0, r = M;
	double md;
	double lm = (1.0)/(double)N/(double)N;
	while (r - l > lm) {
		md = (l + r) / 2;
		if (ck(md))
			r = md;
		else
			l = md;
	}
	ck(l);
	ansit();
}
int main() {
	freopen("hardlife.in", "r", stdin);
	freopen("hardlife.out", "w", stdout);
	init();
	work();
	return 0;
}
//UBWH