#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,m;
struct edge{
	int to,nxt;
}v[340100];
int len,fir[16100];
void add(int x,int y){
	++len;
	v[len]=edge{y,fir[x]};
	fir[x]=len;
}
int dfn[16100],low[16100],id[16100],vis[16100];
int tot,cnt;
stack<int> st;
void dfs(int u){
	dfn[u]=low[u]=++tot;
	st.push(u);
	vis[u]=1;
	for(int i=fir[u];i;i=v[i].nxt){
		if(vis[v[i].to])low[u]=min(low[u],low[v[i].to]);
		else if(!dfn[v[i].to]){
			dfs(v[i].to);
			low[u]=min(low[u],low[v[i].to]);
		}
	}
	if(low[u]==dfn[u]){
		++cnt;
		while(st.top()^u){
			vis[st.top()]=0;
			id[st.top()]=cnt;
			st.pop();
		}
		vis[u]=0;
		id[u]=cnt;
		st.pop();
	}
}
signed main(){
	R(n);R(m);
	n<<=1;
	for(int i=1;i<=n;i+=2){
		add(i+n,i+1);
		add(i+1+n,i);
		add(i,i+1+n);
		add(i+1,i+n);
	}
	while(m--){
		int R(x),R(y);
		add(x,y+n);
		add(y,x+n);
	}
	for(int i=1;i<=n+n;i++)if(!dfn[i])dfs(i);
	bool ans=1;
	for(int i=1;i<=n;i+=2)if(id[i]==id[i+1]||id[i]==id[i+n])ans=0;
	if(!ans){
		puts("NIE");
		return 0;
	}
	for(int i=1;i<=n;i++)if(id[i]<id[i+n])write(i),push('\n');
    return 0;
}