#include<bits/stdc++.h>
using namespace std;
bool w[100007];
int n, m;
class Graph{
  int V;
  list<int> *G;
public:
  Graph(int V)  { this->V = V;  G = new list<int>[V];  }
  ~Graph()      { delete [] G;  }
  void dfs(int a);
  bool is_ok(){
    for(int i = 1;i <= V;i++)
      if(G[i].size() % 2 == 1)
        return 0;
    dfs(1);
    for(int i = 1;i <= n;i++) if(!w[i]) return 0;
    return 1;
  }
  void addEdge(int u, int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }
  void rmvEdge(int u, int v);
  void ET(int s);
  int DFSCount(int v, bool visited[]);
  bool most(int u, int v);
};
void Graph::dfs(int a){
  w[a] = 1;
  for(auto i : G[a])
    if(!w[i])
      dfs(i);
}
void Graph::ET(int u){
  list<int>::iterator i;
  for (i = G[u].begin(); i != G[u].end(); ++i){
    int v = *i;
    if(v != -1 && most(u, v)){
      cout << u << ' ';
      rmvEdge(u, v);
      ET(v);
    }
  }
}
bool Graph::most(int u, int v){
  int count = 0;
  list<int>::iterator i;
  for(i = G[u].begin(); i != G[u].end(); ++i)
    if(*i != -1)
      count++;
  if(count == 1)
    return true;
  bool visited[V];
  memset(visited, false, V);
  int count1 = DFSCount(u, visited);
  rmvEdge(u, v);
  memset(visited, false, V);
  int count2 = DFSCount(u, visited);
  addEdge(u, v);
  return (count1 > count2)? false: true;
}
void Graph::rmvEdge(int u, int v){
  list<int>::iterator iv = find(G[u].begin(), G[u].end(), v);
  *iv = -1;
  list<int>::iterator iu = find(G[v].begin(), G[v].end(), u);
  *iu = -1;
}
int Graph::DFSCount(int v, bool visited[]){
  visited[v] = true;
  int count = 1;
  list<int>::iterator i;
  for (i = G[v].begin(); i != G[v].end(); ++i)
    if (*i != -1 && !visited[*i])
      count += DFSCount(*i, visited);
  return count;
}
int main(){
  cin >> n >> m;
  Graph g(n + 1);
  for(int i = 0, a, b;i < m;i++){
    cin >> a >> b;
    g.addEdge(a, b);
  }
  if(g.is_ok() == 0){
    cout << "NIE";
    return 0;
  }
  cout << "TAK\n";
  g.ET(1);
}