#include<bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=5e5+10;
int x1,x2,Y,y2,top,r,S;
int dfn[N],low[N],st[N],b[N];
bool vis[N];
vector<int>g[N];
inline void add(int u,int v)
{
	g[u].push_back(v);
	return;
}
void tarjan(int u,int fa){
	dfn[u]=low[u]=++top;
	st[++r]=u;
	vis[u]=1;
	for(int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		b[u]=++S;
		vis[u]=0;
		while(st[r]!=u){
			b[st[r]]=S;
			vis[st[r--]]=0;
		}
		r--;
	}
	return;
}
inline int pn(int u)
{	
	if(u%2==0) return (u+1);
	else return (u-1);
}
inline void solve()
{
	int n=read(),m=read();
	F(i,1,m){
		int u=read(),v=read();
		add(u,pn(v));
		add(v,pn(u));
	}
	F(i,1,2*n){
		if(!dfn[i]) tarjan(i,-1);
	}
	for(int i = 1;i<=n*2;i+=2){
		if(b[i]==b[i+1]) {
			printf("NIE\n");
			return;
		}
	}
	for(int i = 1;i<=n*2;i+=2){
		if(b[i]<b[i+1])
        {
            cout<<i<<endl;
        }
        else
        {
            cout<<i+1<<endl;
        }
	}
	return;
}
signed main()
{
	solve();
	return 0;
}