#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

const int N=8005, M=20005;

struct E { int next, to; }e[M<<1];

int cnt, ihead[N<<1], top, s[N<<1], n, m;

bool vis[N<<1];

void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }

bool dfs(int x) {

	if(vis[x^1]) return 0;

	if(vis[x]) return 1;

	vis[x]=1;

	s[++top]=x;

	for(int i=ihead[x]; i; i=e[i].next) if(!dfs(e[i].to)) return 0;

	return 1;

}

bool work() {

	int nn=n<<1;

	for(int i=0; i<nn; i+=2) if(!vis[i] && !vis[i+1]) {

		top=0;

		if(!dfs(i)) {

			while(top) vis[s[top--]]=0;

			if(!dfs(i+1)) return 0;

		}

	}

	for(int i=0; i<nn; ++i) if(vis[i]) printf("%d\n", i+1);

	return 1;

}

int main() {

	while(~scanf("%d%d", &n, &m)) {

		for(int i=0; i<m; ++i) { int x, y; scanf("%d%d", &x, &y); --x; --y; add(x, y^1); add(y, x^1); }

		if(!work()) puts("NIE");

		cnt=top=0;

		memset(vis, 0, sizeof(bool)*(n<<1));

		memset(ihead, 0, sizeof(int)*(n<<1));

	}

	return 0;

}