Beyond the Void

/* 
 * Problem: POI2001 spo
 * Author: Guo Jiabao
 * Time: 2009.1.28 0:58
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAXN=16001,MAXM=36001;
 
struct list
{
	list *next;
	int t;
};
 
struct adjl
{
	list *f,*l;
};
 
adjl A[MAXN];
list L[MAXM];
int N,M,Lc;
bool S[MAXN],TS[MAXN];
 
void addedge(int a,int b)
{
	if (A[a].f)
		A[a].l=A[a].l->next=&L[++Lc];
	else
		A[a].l=A[a].f=&L[++Lc];
	L[Lc].t=b;
}
 
void init()
{
	int i,a,b;
	freopen("spo.in","r",stdin);
	freopen("spo.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
}
 
inline int getop(int k)
{
	if (k%2) return k+1;
	else return k-1;
}
 
bool deal(int a)
{
	int b,bo,ao;
	S[a]=true;
	ao=getop(a);
	if (S[ao])
		return false;
	for (list *k=A[a].f;k;k=k->next)
	{
		b=k->t;
		bo=getop(b);
		if (!S[bo] && !deal(bo))
			return false;
	}
	return true;
}
 
void print(bool k)
{
	if (k)
	{
		for (int i=1;i<=N*2;i++)
			if (S[i])
				printf("%dn",i);
	}
	else
		printf("NIEn");
}
 
void cpy(bool *A,bool *B)
{
	for (int i=1;i<=N*2;i++)
		B[i]=A[i];
}
 
bool solve(int k)
{
	if (!deal(k))
	{
		cpy(TS,S);
		if (!deal(k+1))
			return false;
	}
	cpy(S,TS);
	return true;
}
 
void compute()
{
	for (int i=1;i<=N*2;i+=2)
	{
		if (S[i]==0)
		{
			if (!solve(i))
			{
				print(false);
				return;
			}
		}
	}
	print(true);
}
 
int main()
{
	init();
	compute();
	return 0;
}