#include<bits/stdc++.h>
using namespace std;
vector<int> graf[100005];
int odw[100005];
int gdzie[100005];
int rep[100007];
int Find(int a){
if(rep[a] == a){
return a;
}
rep[a] = Find(rep[a]);
return (rep[a]);
}
int Union(int a,int b){
if(Find(a) == Find(b))
{
rep[Find(a)] = rep[Find(b)];
return 1;
}
rep[Find(a)] = rep[Find(b)];
return 0;
}
void dfs(int w,int od,int dor)
{
odw[w] = 1;
for(int i : graf[w])
{
if(w == od && i == dor) continue;
if(w == dor && i == od) continue;
if(odw[i] == 0)
{
dfs(i,od,dor);
gdzie[i] = w;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n,m,a,b,x,y;
cin >> n >> m;
for(int i = 0;i < m;++i)
{
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
if(Union(a,b) == 1)
{
x =a;y=b;
}
}
dfs(x,x,y);
gdzie[x] = y;
int l = rep[Find(1)];
for(int i = 1; i <= n;++i)
{
if(gdzie[i] == 0)
{
cout << "NIE";
return 0;
}
if(rep[Find(i)] != l){ cout << "NIE"; return 0; }
}
cout << "TAK" << endl;
for(int i = 1; i <= n;++i)
{
cout << gdzie[i] << endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2ZWN0b3I8aW50PiBncmFmWzEwMDAwNV07CmludCBvZHdbMTAwMDA1XTsKaW50IGdkemllWzEwMDAwNV07CmludCByZXBbMTAwMDA3XTsKCmludCBGaW5kKGludCBhKXsKCQoJaWYocmVwW2FdID09IGEpewoJCXJldHVybiBhOwoJfQoJcmVwW2FdID0gRmluZChyZXBbYV0pOwoJcmV0dXJuIChyZXBbYV0pOwp9CgoKaW50IFVuaW9uKGludCBhLGludCBiKXsKICAgIGlmKEZpbmQoYSkgPT0gRmluZChiKSkKICAgIHsKICAgICAgICByZXBbRmluZChhKV0gPSByZXBbRmluZChiKV07CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICAKCXJlcFtGaW5kKGEpXSA9IHJlcFtGaW5kKGIpXTsKCXJldHVybiAwOwp9Cgp2b2lkIGRmcyhpbnQgdyxpbnQgb2QsaW50IGRvcikKewogICAgb2R3W3ddID0gMTsKICAgIGZvcihpbnQgaSA6IGdyYWZbd10pCiAgICB7CiAgICAgICAgaWYodyA9PSBvZCAmJiBpID09IGRvcikgY29udGludWU7CiAgICAgICAgaWYodyA9PSBkb3IgJiYgaSA9PSBvZCkgY29udGludWU7CiAgICAgICAgaWYob2R3W2ldID09IDApCiAgICAgICAgewogICAgICAgICAgICBkZnMoaSxvZCxkb3IpOwogICAgICAgICAgICBnZHppZVtpXSA9IHc7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBpbnQgbixtLGEsYix4LHk7CiAgICBjaW4gPj4gbiA+PiBtOwogICAgZm9yKGludCBpID0gMDtpIDwgbTsrK2kpCiAgICB7CiAgICAgICAgY2luID4+IGEgPj4gYjsKICAgICAgICBncmFmW2FdLnB1c2hfYmFjayhiKTsKICAgICAgICBncmFmW2JdLnB1c2hfYmFjayhhKTsKICAgICAgICBpZihVbmlvbihhLGIpID09IDEpCiAgICAgICAgewogICAgICAgIAl4ID1hO3k9YjsKICAgICAgICAJCiAgICAgICAgfQogICAgfQogICAgZGZzKHgseCx5KTsKICAgIGdkemllW3hdID0geTsKICAgIGludCBsID0gcmVwW0ZpbmQoMSldOwogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOysraSkKICAgIHsKICAgIAlpZihnZHppZVtpXSA9PSAwKQogICAgCXsKICAgIAkJY291dCA8PCAiTklFIjsKICAgIAkJcmV0dXJuIDA7CiAgICAJfQogICAgCWlmKHJlcFtGaW5kKGkpXSAhPSBsKXsgY291dCA8PCAiTklFIjsgcmV0dXJuIDA7IH0KICAgIH0KICAgIGNvdXQgPDwgIlRBSyIgPDwgZW5kbDsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsrK2kpCiAgICB7CiAgICAJY291dCA8PCBnZHppZVtpXSA8PCBlbmRsOwogICAgfQogICAgCiAgICAKICAgIAp9