#include <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = 16100;

struct node {

     int v,next;

} edge[41000];

int head[maxn],sta[maxn],vis[maxn];

int id,top,n;

void add_edge(int u,int v){

     edge[id].v = v;edge[id].next = head[u];head[u] = id++;

}

int dfs(int u){

    if( vis[u^1] )return 0;

    if( vis[u])return 1;

    vis[u] = 1;

    sta[top++] = u;

    for(int id = head[u]; id != -1; id = edge[id].next)

    if(!dfs(edge[id].v))return 0;

    return 1;

}

int slove(){

    memset(vis,0,sizeof(vis));

    for(int v = 0; v < n*2; v += 2){

        if( vis[v] || vis[v^1])continue;

        top = 0;

        if(!dfs(v)){

            while(top)vis[sta[--top]] = 0;

            if( !dfs(v^1))return 0;

        }

    }

    return 1;

}

int main()

{

     int m;

     int u,v;

     while(~scanf("%d%d",&n,&m)) {

          memset(head,-1,sizeof(head));

          id = 0;

          for(int i = 0; i < m; i ++) {

               scanf("%d%d",&u,&v);

            u--;v--;

            add_edge(u,v^1);

            add_edge(v,u^1);

          }

          if( !slove())puts("NIE");

          else {

                for(int i = 0; i < n*2; i+= 2){

                    printf("%d\n",(vis[i]?i:i^1) + 1);

                }

          }

     }

     return 0;

}