#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 8005
#define MAXN 400005
#define OO (1<<31)-1
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

struct TwoSAT
{
    int n;
    vector<int>g[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x)
    {
        if(mark[x^1]) return false ;
        if(mark[x]) return true ;
        mark[x]=true ;
        S[c++]=x;
        for(int i=0; i<g[x].size(); i++)
        {
            if(!dfs(g[x][i])) return false ;
        }
        return true ;
    }
    void init(int n)
    {
        this->n=n;
        for(int i=0; i<n*2; i++) g[i].clear();
        memset(mark,0,sizeof(mark));
    }
    void add_clause(int x,int xval,int y,int yval)
    {
        x=x*2+xval;
        y=y*2+yval;
        g[x^1].push_back(y);
        g[y^1].push_back(x);
    }
    bool solve()
    {
        for(int i=0; i<n*2; i+=2)
        {
            if(!mark[i]&&!mark[i+1])
            {
                c=0;
                if(!dfs(i))
                {
                    while(c>0) mark[S[--c]]=false ;
                    if(!dfs(i+1)) return false ;
                }
            }
        }
        return true ;
    }
};

int n,m,sum;
int age[maxn];
TwoSAT ts;

int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        ts.init(n);
        int u,v,x,y;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            u--;
            v--;
            ts.g[u].push_back(v^1);
            ts.g[v].push_back(u^1);
        }
        if(ts.solve())
        {
            for(i=0; i<n*2; i+=2)
            {
                if(ts.mark[i]) printf("%d\n",i+1);
                else printf("%d\n",i+2);
            }
        }
        else puts("NIE");
    }
    return 0;
}