#include<bits/stdc++.h>
#define int long long
#define PII pair< int, int >

using namespace std;

const int N = 1e6 + 5, mod = 998244353;
int n, m, h[N], e[N], ne[N], idx = 1;
int dfn[N], low[N], clr, clrnum[N], cnt, flag[N];
bool vis[N], s[N];
stack< int > stk;

template< typename T >inline void read(T &x){bool f=1;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=(f?x:-x);return;}
template< typename T, typename ... L > void read(T &a , L && ... b) { read(a); read(b ...); }
int ksm(int a, int b, int p){int ans = 1;while(b){if(b & 1)ans =(ans*a)%p;b >>= 1;a = (a*a) % p;}return ans;}
void add(int u, int v){
	e[idx] = v;
	ne[idx] = h[u];
	h[u] = idx++;
}
void tarjan(int u){
	stk.push(u);
	vis[u] = s[u] = true;
	dfn[u] = low[u] = ++cnt;
	for (int i = h[u]; ~i; i = ne[i]){
		int v = e[i];
		if (!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		clr++;
		while (stk.top() != u){
			clrnum[clr]++;
			vis[stk.top()] = false;
			flag[stk.top()] = clr;
			stk.pop();
		}
		clrnum[clr]++;
		vis[stk.top()] = false;
		flag[stk.top()] = clr;
		stk.pop();
	}
}
signed main(){
//	freopen("a.in", "r", stdin);
//	freopen("a.out","w",stdout);
	read(n, m);
	memset(h, -1, sizeof h);
	for (int k = 1; k <= m; k++){
		int a, b;
		read(a, b);
		int a1 = (a - 1) % 2, b1 = (b - 1) % 2; 
		if (a == 1 && b == 1){
			add(a, b - 1);
			add(b, a - 1);
		}
		else if (a == 1 && b == 0){
			add(a, b + 1);
			add(b, a - 1);
		}
		else if (a == 0 && b == 1){
			add(a, b - 1);
			add(b, a + 1);
		}
		else {
			add(a, b + 1);
			add(b, a + 1);
		}
	}
	for (int i = 1; i <= 2 * n; i++){
		if (!s[i])
			tarjan(i);
	}
	for (int i = 1; i <= n; i++){
		if (flag[2 * i - 1] == flag[2 * i]){
			printf("NIE");
			return 0;
		}
	}
	for (int i = 1; i <= n; i++){
		if (flag[2 * i - 1] < flag[2 * i]) printf("%lld\n", 2 * i - 1);
		else printf("%lld\n", 2 * i);
	}
	return 0;
}