记录编号	461308	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.392 s
提交时间	2017-10-19 19:44:05	内存使用	0.80 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define anti(x)  (x&1)?(x+1):(x-1)
using namespace std;
const int sj=16010;
int n,m,h[sj],e,st[sj],a1,a2,ans[sj];
struct B
{
    int ne,v;
}b[20010<<1];
void add(int x,int y)
{
     b[e].v=y,b[e].ne=h[x],h[x]=e++;
}
bool paint(int x)
{
     if(st[x]!=0)  return st[x]==1;
     st[x]=1,st[anti(x)]=2;
     ans[++a2]=x;
     for(int i=h[x];i!=-1;i=b[i].ne)
          if(!paint(b[i].v))
             return 0;  
     return 1;
}
bool work()
{
     for(int i=1;i<=2*n;i++)
     {
         if(st[i])  continue;
         a2=0;
         if(!paint(i))
         {
             for(int j=1;j<=a2;j++)
                 st[ans[j]]=st[anti(ans[j])]=0;
             if(!paint(anti(i)))  return 0;
         }
     }
     return 1;
}
int main()
{
    //freopen("t.txt","r",stdin);
    freopen("spo.in","r",stdin);
    freopen("spo.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a1,&a2);
        add(a1,anti(a2));
        add(a2,anti(a1));
    }
    if(work())
    {
        for(int i=1;i<=n*2;i++)
            if(st[i]==1)
               printf("%d\n",i);
    }
    else printf("NIE");
    //while(1);
    return 0;
}