clo

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int n,m,a,b,wynik[100001],par[100001];
pair <int,int> cykl;
bitset <100001> odw;
vector <int> v[100001];
vector <int> v1[100001];
vector <int> w;
vector <pair<int,int> > t;
void szukaj(int x,int y)
{
w.push_back(x);

    odw[x]=1;
    for(int j=0;v[x].size()>j;j++)
    {
        if(odw[v[x][j]]==1 and v[x][j]!=y and cykl.first==0)
        {
            cykl.first=v[x][j];
            cykl.second=x;

        }
        if(odw[v[x][j]]==0)
            szukaj(v[x][j],x);
    }
}
void bfs(int x,int y)
{

    for(int i=0;v1[x].size()>i;i++)
    {
        if(v1[x][i]!=y)
        {
            wynik[v1[x][i]]=x;
            bfs(v1[x][i],x);

        }
    }
}
int Find(int x)
{
    if(par[x]==x)
    return x;
   par[x]=Find(par[x]);
    return par[x];
}
void Union(int h,int j)
{
    par[Find(h)]=Find(j);
}
int main()
{
cin>>n>>m;
for(int i=1;m>=i;i++)
    par[i]=i;
for(int i=0;m>i;i++)
{
    cin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);
    t.push_back({a,b});
}

for(int i=1;n>=i;i++)
{
    if(odw[i]==0)
    {

        cykl.first=0;
        cykl.second=0;
        w.clear();

        szukaj(i,-1);

        if(cykl.first==0)
        {
            cout<<"NIE";
            return 0;
        }

       wynik[cykl.first]=cykl.second;

       for(int b=0;w.size()>b;b++)
       {
for(int g=0;v[w[b]].size()>g;g++)
{

           if(v[w[b]][g]>w[b] and Find(v[w[b]][g])!=Find(w[b]) and !(w[b]==cykl.first and v[w[b]][g]==cykl.second) and !(w[b]==cykl.second and v[w[b]][g]==cykl.first))
           {

               v1[w[b]].push_back(v[w[b]][g]);
               v1[v[w[b]][g]].push_back(w[b]);
               Union(w[b],v[w[b]][g]);
           }
       }
       }

       bfs(cykl.first,-1);
    }
}
cout<<"TAK\n";
for(int i=1;n>=i;i++)
    cout<<wynik[i]<<endl;
    return 0;
}