1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 using namespace std;

 6 const int maxn=16020;

 7 const int maxm=4e4+20;

 8 int n,m;

 9 struct edge

10 {

11     int u,v,nxt;

12 }e[maxm];

13 int head[maxn],js;

14 void addage(int u,int v)

15 {

16     e[++js].u=u;e[js].v=v;

17     e[js].nxt=head[u];head[u]=js;

18 }

19 int clo[maxn],st[maxn],top;

20 bool dfs(int x)

21 {

22     if(clo[x]==1)return 1;

23     if(clo[x]==2)return 0;

24     clo[x]=1;clo[x^1]=2;

25     st[++top]=x;

26     for(int i=head[x];i;i=e[i].nxt)

27     {

28         int v=e[i].v;

29         if(!dfs(v))return 0;

30     }

31     return 1;

32 }

33 bool sat()

34 {

35     memset(clo,0,sizeof clo);

36     for(int i=0;i<(n<<1);i+=2)

37     {

38         if(clo[i])continue;

39         top=0;

40         if(!dfs(i))

41         {

42             while(top)clo[st[top]]=0,clo[st[top--]^1]=0;

43             if(!dfs(i^1))return 0;

44         }

45     }

46     return 1;

47 }

48 void init()

49 {

50     memset(head,0,sizeof head);

51     js=0;

52     memset(clo,0,sizeof clo);

53     memset(st,0,sizeof st);

54

55 }

56 int main()

57 {

58     while(scanf("%d%d",&n,&m)==2)

59     {

60         init();

61         for(int a,b,i=1;i<=m;++i)

62         {

63             scanf("%d%d",&a,&b);

64             --a,--b;

65             addage(a,b^1);

66             addage(b,a^1);

67         }

68         if(sat())

69         {

70             for(int i=0;i<=(n<<1);++i)

71                 if(clo[i]==1)printf("%d\n",i+1);

72         }

73         else puts("NIE");

74     }

75     return 0;

76 }