#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

int num,ne[N],fi[N],n,m,x,y,f[N],zz[N],vis[N],S[N],top;

void jb(int x,int y)

{

    ne[++num]=fi[x];

    fi[x]=num;

    zz[num]=y;

}

int dfs(int x)

{

    if (vis[x^])return ;

    if (vis[x])return ;

    vis[x]=;

    S[top++]=x;

    for (int i=fi[x];i;i=ne[i])

     if (!dfs(zz[i]))return ;

    return ;

}

int slove()

{

    memset(vis,,sizeof vis);

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

     {

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

          top=;

          if (!dfs(i))

           {

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

               if (!dfs(i^))return ;

           }

     }

    return ;

}

int main()

{

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

      {

          memset(fi,,sizeof fi);

          num=;

        while (m--)

          {

             scanf("%d%d",&x,&y);

             x--;y--;

             jb(x,y^);jb(y,x^);

          }

        if (slove())

          {

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

               if (vis[i])printf("%d\n",i+);

          }

        else puts("NIE");

     }

    return ;

}