#include<bits/stdc++.h>
using namespace std;
bitset<100007> w(0); //odwiedzone wierzcho³ki
bitset<250007> most(0); //mosty
vector<pair<int, int>> G[100007];
vector<int> cykl_eulera;
int low[100007], preorder[100007], nr;
void DFS(int v = 1, int p = -1) {
    w[v] = 1;
    preorder[v] = low[v] = nr++;
    for(auto i : G[v]){
      if(i.first == p) continue;
      if(w[i.first]) low[v] = min(low[v], preorder[i.first]);
      else{
        DFS(i.first, v);
        low[v] = min(low[v], low[i.first]);
        if(low[i.first] > preorder[v])
          most[i.second] = 1;
      }
    }
}
void update(){
  w.reset();
  most.reset();
  nr = 0;
  DFS();
}
void skasuj(int v, int u){
  for(int i = 0;i < G[v].size();i++)
    if(G[v][i].first == u){
      swap(G[v][i], G[v].back());
      G[v].pop_back();
    }
  for(int i = 0;i < G[u].size();i++)
    if(G[u][i].first == v){
      swap(G[u][i], G[u].back());
      G[u].pop_back();
    }
}
void cykl(){
  int v = 1;
  bool z;
  while(!G[v].empty()){
    update();
    z = 0;
    cykl_eulera.push_back(v);
    for(auto i : G[v]){
      if(most[i.second]) continue;
      skasuj(v, i.first);
      v = i.first;
      z = 1;
      break;
    }
    if(z) continue;
    for(auto i : G[v]){
      skasuj(v, i.first);
      v = i.first;
      break;
    }
  }
}
void dfs(int a){
  w[a] = 1;
  for(auto i : G[a])
    if(!w[i.first])
      DFS(i.first);
}
bool spojny(int n){
  dfs(1);
  for(int i = 1;i <= n;i++) if(!w[i]) return 0;
  return 1;
}
int main(){
  int n, m; //wierzchokli, krawedzie
  cin >> n >> m;
  for(int i = 0, a, b;i < m;i++){
    cin >> a >> b;
    G[a].emplace_back(b, i);
    G[b].emplace_back(a, i);
  }
  for(int i = 1;i <= n;i++)
    if(G[i].size() % 2 == 1 || G[i].size() == 0){
      cout << "NIE";
      return 0;
    }
  if(!spojny(n) || m < n){
    cout << "NIE";
    return 0;
  }
  cykl();
  if(cykl.size() != m){
    cout << "NIE";
    return 0;
  }
  cout << "TAK\n";
  for(auto i : cykl_eulera)
    cout << i << ' ';
}