RT

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
	int to,next;
}e[40005];
int first[40005],np=0,now_size,oth[40005];
bool vis[40005],nie=0;
stack<int>stk;
vector<int>ans;
void add(int x,int y)
{
	e[++np]=(edge){y,first[x]};
    first[x]=np;
}
void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2*n;i++)
	{
		if(i%2==1)oth[i]=i+1;
		else oth[i]=i-1;
	}
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,oth[b]);
		add(b,oth[a]);
	}
}
bool dfs(int x)
{
	if(vis[x])return 1;
	if(vis[oth[x]])return 0;
	stk.push(x);
	now_size++;
	vis[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int j=e[i].to;
		if(!dfs(j))return 0;
	}
	return 1;
}
void twosat()
{
	for(int i=1;i<=n;i++)
	{
		if(vis[2*i-1]||vis[2*i])continue;
		now_size=0;
		if(!dfs(2*i-1))
		{
			for(int j=1;j<=now_size;j++)
			{
				int x=stk.top();
				stk.pop();
				vis[x]=0;
			}
			if(!dfs(2*i))
			{
				nie=1;
				return;
			}
		}
	}
}
void output()
{
	if(nie)
	{
		printf("NIE");
		return;
	}
	while(!stk.empty())
	{
		int x=stk.top();
		ans.push_back(x);
		stk.pop();
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++)
	    printf("%d\n",ans[i]);
}
int main()
{
	init();
	twosat();
	output();
	return 0;
}