#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<ctime>
#define R read()
#define V inline void
#define fr for
#define debug(x) cout<<x<<endl;
using namespace std;
clock_t start,end;
int T,N,M;
char a,b;
const int maxn=4e3+10;
const int mmm=16010;;
int head[mmm],to[maxn],nxt[maxn],cnt;
int dfn[mmm],low[mmm],timestep;
int s[maxn],top,in_s[mmm];
int scc_cnt;
int id[mmm];
int scc[maxn];
int x,y;
bool flag;
V add(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
V clea(){
	memset(head,-1,sizeof(head));
	cnt=timestep=scc_cnt=0;
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(id,0,sizeof(id));
	flag=0;
	
}
int partener(int x){
	if (x % 2 == 1) return x + 1;
	return x - 1; 
}
V tarjin(int u){
	dfn[u]=low[u]=++timestep;
	in_s[u]=1,s[++top]=u;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjin(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in_s[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++scc_cnt;
		id[u]=scc_cnt;
		in_s[u]=0;
		while(s[top]!=u){
			id[s[top]]=scc_cnt;
			in_s[s[top]]=0;
			--top;
		}
		--top;
	}
}
int leo(){
//	freopen("P4171_4.in","r",stdin);
//	freopen("1.txt","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		add(x,partener(y));
		add(y,partener(x));
	}
	for(int i=1;i<=N*2;++i){
		if(!dfn[i])
			tarjin(i);
	}
//	for(int i=1;i<=N*2;++i)
//		cout<<id[i]<<endl;
	for(int i=1;i<=N*2;i+=2){
		if(id[i]==id[i+1])
		{
			cout<<"NIE";
			return 0;
		}
	}
	for(int i=1;i<=N*2;i+=2){
		if(id[i]<id[i+1])
			cout<<i<<endl;
		else
			cout<<i+1<<endl;
	}
}
int m=leo();
signed main(){;}