板。

const int N = 3e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int head[N], tot;
	struct Edge {
		int to, nxt;
	} e[N << 2];
	void add_edge (int u, int v) { e[++tot] = (Edge) {v, head[u]}, head[u] = tot; }
	int dfn[N], low[N], stk[N], top, cnt;
	int col[N], ccnt;
	bool vis[N];
	void Tarjan (int u) {
		dfn[u] = low[u] = ++cnt;
		stk[++top] = u; vis[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			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]) {
			ccnt++;
			for (; stk[top] != u; top--) {
				vis[stk[top]] = 0;
				col[stk[top]] = ccnt;
			}
			vis[u] = 0;
			col[u] = ccnt;
			top--;
		}
	}
	int main () {
		n = Read() * 2, m = Read();
		for (int i = 1; i <= n; i += 2) 
			add_edge(i + n, i + 1), add_edge(i + 1 + n, i), add_edge(i, i + 1 + n), add_edge(i + 1, i + n);
		for (int i = 1; i <= m; i++) {
			int x = Read(), y = Read();
			add_edge (x, y + n), add_edge(y, x + n);
		}
		for (int i = 1; i <= n * 2; i++) if (!dfn[i]) Tarjan (i);
		for (int i = 1; i <= n; i++) if (col[i] == col[i + n]) return puts("NIE") & 0;
		for (int i = 1; i <= n; i++) if (col[i] < col[i + n]) printf ("%d\n", i);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}