记录编号	190227	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	_stranger	是否通过	通过
代码语言	C++	运行时间	0.370 s
提交时间	2015-10-02 20:16:52	内存使用	0.58 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
inline int read(){
    int x=0;char ch;
    while(!isdigit(ch=getchar()));x=ch-48;
    while(isdigit(ch=getchar()))x=x*10+ch-48;
    return x;
}
bool b[40001],set[40001];
vector<int>a[16001];
int n,m;
bool judge(int x){
    if(b[x])return 1;
    b[x]=1;
    if(set[x])return 1;
    if(set[x^1]) return 0;
    if(b[x^1]) return 0;
    for(int i=0;i<a[x].size();i++){
//        cout<<a[x][i]<<' '<<x<<' '<<i<<endl;
        if(!judge(a[x][i]))

        return 0;
    }
    return 1;
}
void work(int x){
    if(set[x])return;
    set[x]=1;
    for(int i=0;i<a[x].size();i++)work(a[x][i]);
}
int main(){
    freopen("spo.in","r",stdin);freopen("spo.out","w",stdout);
    n=2*read();m=read();
    int x,y;
    for(int i=1;i<=m;i++){
        x=read()-1;y=read()-1;//cout<<x<<' '<<y<<endl;
        a[x].push_back(y^1);
        a[y].push_back(x^1);
    }
    for(int i=0;i<n;i+=2){
        memset(b,0,sizeof b);//cout<<i;
        if(judge(i))work(i);
        else{//cout<<i<<' ';
            memset(b,0,sizeof b);
            if(!judge(i^1)){
                puts("NIE");//while(1);
                return 0;
            }else work(i^1);
        }
    }
    for(int i=0;i<n;i++)
        if(set[i])
            printf("%d\n",i+1);//while(1);
    return 0;
}