#include <bits/stdc++.h>
using namespace std;
const int N=16003,M=400003;
int df[N],lo[N],sdd,cnt;
int he[N],ne[M],e[M],d;
int dy[N],ql[N];
int n,m;
int q[N],to;
bool f[N];
void add(int x,int y)
{
	ne[++d]=he[x];
	he[x]=d;
	e[d]=y;
}
void s(int u)
{
	df[u]=lo[u]=++cnt;
	f[u]=true;
	q[++to]=u;
	for(int i=he[u];i;i=ne[i])
	{
		int o=e[i];
		if(df[o]==0)
		{
			s(o);
			lo[u]=min(lo[u],lo[o]);
		}
		else if(f[o])lo[u]=min(lo[u],lo[o]);
	}
	if(df[u]==lo[u])
	{
		int y;
		++sdd;
		do{
			y=q[to--];
			f[y]=false;
			ql[y]=sdd;
		}while(y!=u);
	}
}
int rd[N],tp[N];
int ha[N],na[M],ea[M],ad;
void ada(int x,int y)
{
	na[++ad]=x;
	ha[x]=ad;
	ea[ad]=y;
}
int pp[N*10],h=0,end=-1;
int yf[N];
void top()
{
	for(int i=1;i<=sdd;i++)
	{
		if(rd[i]==0)
		{
			pp[++end]=i;
			yf[i]=true;
			tp[i]=1;
		}
	}
	while(h<=end)
	{
		int u=pp[h++];
		for(int i=ha[u];i;i=na[i])
		{
			int o=ea[i];
			if(yf[o])continue;
			rd[o]--;
			if(rd[o]==0)
			{
				pp[++end]=o;
				yf[o]=true;
				tp[o]=tp[u]+1;
			}
		}
	}
}
bool fff[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		dy[i*2-1]=2*i;
		dy[i*2]=i*2-1;
	}
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,dy[b]);
		add(b,dy[a]);
	}
	for(int i=1;i<=2*n;i++)if(!f[i])s(i);
	for(int i=1;i<=2*n;i+=2)
	{
		if(ql[i]==ql[i+1])
		{
			cout<<"NIE";
			return 0;
		}
	}
	for(int i=1;i<=2*n;i++)
	{
		for(int j=he[i];j;j=ne[j])
		{
			int x=ql[i],y=ql[e[j]];
			ada(x,y);
			rd[y]++;
		}
	}
	top();
	for(int i=1;i<=n;i++)
	{
		if(tp[ql[i*2-1]]<tp[ql[i*2]])
		{
			cout<<i*2<<endl;
		}
		else cout<<i*2-1<<endl;
	}
	return 0;
}