#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define lson(x) ((x<<1))

#define rson(x) ((x<<1)+1)

using namespace std;

typedef long long ll;

const int N=2e4+;

const int M=4e5+;

struct Edge {

    int to,next;

} edge[M];

int head[M],tot;

void init() {

    tot = ;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v) {

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

bool vis[N];//染色标记，为true表示选择

int S[N],top;//栈

bool dfs(int u) {

    if(vis[u^])return false;

    if(vis[u])return true;

    vis[u] = true;

    S[top++] = u;

    for(int i = head[u]; i != -; i = edge[i].next)

        if(!dfs(edge[i].to))

            return false;

    return true;

}

bool Twosat(int n) {

    memset(vis,false,sizeof(vis));

    for(int i = ; i < n; i += ) {

        if(vis[i] || vis[i^])continue;

        top = ;

        if(!dfs(i)) {

            while(top)vis[S[--top]] = false;

            if(!dfs(i^)) return false;

        }

    }

    return true;

}

int main() {

    int n,m;

    int u,v;

    scanf("%d%d",&n,&m);

    init();

    while(m--) {

        scanf("%d%d",&u,&v);

        u--;

        v--;

        addedge(u,v^);

        addedge(v,u^);

    }

    if(Twosat(*n)) {

        for(int i = ; i < *n; i++)

            if(vis[i])

                printf("%d\n",i+);

    } else printf("NIE\n");

    return ;

}