记录编号	223897	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2016-02-14 14:52:44	内存使用	0.73 MiB

#include<stdio.h>
bool mark[16010];
int n,m,shu,first[16010],s[16010];
struct edge{int v,nx;}o[40010];
inline void add(int u,int v){o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;}
inline bool dfs(int p){
	if(mark[((p-1)^1)+1]) return 0;
	if(mark[p]) return 1;
	mark[p]=1,s[++s[0]]=p;
	for(int i=first[p];i;i=o[i].nx) if(!dfs(o[i].v)) return 0;
	return 1;
}
inline bool work(){
	for(int i=1,a,b;i<=n;++i){
		b=i<<1,a=b-1;
		if((!mark[a])&&(!mark[b])){
			s[0]=0;
			if(!dfs(a)){
				while(s[0]) mark[s[s[0]--]]=0;
				if(!dfs(b)) return 0;
			}
		}
	}
	return 1;
}
int main(){
	freopen("spo.in","r",stdin);freopen("spo.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0,a,b;i<m;++i) scanf("%d%d",&a,&b),add(a,((b-1)^1)+1),add(b,((a-1)^1)+1);
	if(work()){
		n<<=1;
		for(int i=1;i<=n;++i) if(mark[i]) printf("%d\n",i);
	}
	else puts("NIE");
}