//Spokojna Komisja
//VIII OI
#include <cstdio>
#include <vector>
#include <algorithm>
#define KOL(x) ((x&1)?(x+1):(x-1))
using namespace std;
const int N = 16001;
int n,m,ile_sss;
int vis[N],sss[N],wyj[N],w[N];
//sss[i] - numer sss w ktorej jest wierzcholek i
//wyj[i] - stopien wyjscia (graf sss)
//w[i] = 0, gdy sss i jeszcze nie przetworzona, 1 gdy brana do parl, -1 gdy nie brana do parl (graf sss)
vector<int> G[N];
vector<int> Gr[N];//graf odwrocony do sss
vector<int> sssv[N];//w sssv[i] znajduje sie lista wierzcholkow w sss o numerze i
vector<int> H[N];//graf odwrocony do grafu utworzonego przez sss
vector<int> q,post;
//q - "kolejka" wierzcholkow do przetworzenia, o stopniu wyjscia 0 (graf sss)
//post - kolejnosc post-order do wyznaczania sss
void dfs_post(int x)
{
  static int cnt=1;
  vis[x] = 1;
  for (int i=0;i<G[x].size();i++)
    if (!vis[G[x][i]])
      dfs_post(G[x][i]);
  post.push_back(x);
}
void dfs_sss(int x)
{
  for (int i=0;i<Gr[x].size();i++)
    if (!sss[Gr[x][i]])
    {
      sss[Gr[x][i]] = ile_sss;
      sssv[ile_sss].push_back(Gr[x][i]);
      dfs_sss(Gr[x][i]);
    }
}
void wczytaj()
{
  scanf("%d %d",&n,&m);
  for (int i=0;i<m;i++)
  {
    int x,y;
    scanf("%d %d",&x,&y);
    G[x].push_back(KOL(y));
    Gr[KOL(y)].push_back(x);
    G[y].push_back(KOL(x));
    Gr[KOL(x)].push_back(y);
  }
}
void wyznacz_sss()
{
  for (int i=1;i<=2*n;i++)
  {
    if (!vis[i])
      dfs_post(i);
  }
  for (int i=2*n-1;i>=0;i--)
  {
    if (!sss[post[i]])
    {
      sss[post[i]] = ++ile_sss;
      sssv[ile_sss].push_back(post[i]);
      dfs_sss(post[i]);
    }
  }
}
void utworz_graf_sss()
{
  for (int i=1;i<=2*n;i++)
  for (int j=0;j<G[i].size();j++)
    if (sss[i] != sss[G[i][j]])
    {
      H[sss[G[i][j]]].push_back(sss[i]);
      wyj[sss[i]]++;   
    } 
}
void przeglad_w_porz_top()
{
  for (int i=1;i<=ile_sss;i++)
    if (wyj[i]==0) q.push_back(i);
  for (int i=1;i<=n;i++)
  {
    if (sss[2*i] == sss[2*i-1]) 
    {
      printf("NIE\n");
      return;
    }
  }
  int x;
  while (!q.empty())
  {
    x = q[q.size()-1];
    q.pop_back();
    if (w[x] == 0)
    {
      w[x] = 1; //bierzemy skladowa x
      for (int i=0;i<sssv[x].size();i++)  //bierzemy kazdy element skladowej x
	w[sss[KOL(sssv[x][i])]] = -1; //ale skladowa z elementem x' juz odrzucamy
    }
    //przetworzylismy 
    for (int i=0;i<H[x].size();i++)
    {
      wyj[H[x][i]]--;
      if (wyj[H[x][i]] == 0) q.push_back(H[x][i]);
    }
  }
  for (int i=1;i<=2*n;i++)
    if (w[sss[i]]==1)
      printf("%d\n",i);
}
int main()
{
  wczytaj();
  wyznacz_sss();
  utworz_graf_sss();
  przeglad_w_porz_top();
  return 0;
}