记录编号	468636	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.375 s
提交时间	2017-11-01 16:37:50	内存使用	1.00 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 20050
#define ops(_) ((_&1)?(_+1):(_-1))
using namespace std;
int n,m;
int e=1,head[N];
struct edge{int u,v,next;}ed[2*N];
void add(int u,int v){
    ed[e].u=u;ed[e].v=v;
    ed[e].next=head[u];
    head[u]=e++;
}
int c[N];
int ans[N],cnt;
bool dfs(int x){
	if(c[x])return c[x]&1;
	c[x]=1; c[ops(x)]=2;
	ans[++cnt]=x;
	for(int i=head[x];i;i=ed[i].next)
		if(!dfs(ed[i].v))return 0;
	return 1;
}
int main(){
    freopen("spo.in","r",stdin);
    freopen("spo.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		add(u,ops(v)); add(v,ops(u));
	}
	for(int i=1;i<=2*n;i++){
		if(c[i])continue;
		cnt=0;
		if(!dfs(i)){
			for(int j=1;j<=cnt;j++)c[ans[j]]=c[ops(ans[j])]=0;
			if(!dfs(ops(i))){puts("NIE");return 0;}
		}
	}
	for(int i=1;i<=2*n;i++)
		if(c[i]==1)printf("%d\n",i);
    return 0;
}