#include<bits/stdc++.h>
using namespace std;
const int M=1e6+7;
int n,m,a,b,p[M],eid,s[M],c,choose[M];
struct node{
	int u,v,next;
}e[M];
void insert(int u,int v){
	e[++eid].u=u;e[eid].v=v;
	e[eid].next=p[u];p[u]=eid;
}
bool dfs(int u){
	if(choose[((u%2)?u+1:u-1)])return false;
	if(choose[u])return true;
	s[c++]=u;choose[u]=true;
	for(int i=p[u];i;i=e[i].next)if(!dfs(e[i].v))return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		insert(a,((b%2)?b+1:b-1));
		insert(b,((a%2)?a+1:a-1));
	}
	for(int i=1;i<=2*n;i+=2){
		if(!choose[i]&&!choose[i+1]){
			c=0;
			if(!dfs(i)){
				while(c>0)choose[s[--c]]=false;
				if(!dfs(i+1)){printf("NIE\n");return 0;}
			}
		}
	}
	for(int i=1;i<=2*n;i++)if(choose[i])printf("%d\n",i);
	return 0;
}

在机房里写了1个小时tarjan优化版本没调出来索性贴了个暴力上去还AC了