#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=1e6+10;
stack<int>st;
vector<int>g[maxn];
int dfn[maxn],low[maxn],cnt,belong[maxn],scc;
bool instack[maxn];
void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	st.push(u);instack[u]=1;
	for(int v:g[u]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(instack[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		++scc;
		while(1){
			int v=st.top();
			st.pop();
			instack[v]=0;
			belong[v]=scc;
			if(v==u)break; 
		}
	}
}
#define T(x) (x)
#define F(x) (x+2*n)
#define partner(x) (x%2==0?x-1:x+1)
int n,m;
int main(){
	int a,b;
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>a>>b;
		g[T(a)].push_back(F(b));
		g[T(b)].push_back(F(a));
		g[T(a)].push_back(T(partner(b)));
		g[T(b)].push_back(T(partner(a)));
	} 
	for(int i=1;i<=n;++i)g[T(2*i)].push_back(F(2*i-1)),g[T(2*i-1)].push_back(F(2*i));
	for(int i=1;i<=n*4;++i)if(!dfn[i])tarjan(i);
	for(int i=1;i<=2*n;++i)if(belong[T(i)]==belong[F(i)]){cout<<"NIE";return 0;}
	for(int i=1;i<=n;++i){
		if(belong[T(2*i)]<belong[T(2*i-1)])cout<<2*i<<"\n";
		else cout<<2*i-1<<"\n";
	}
	return 0;
}