#include <bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
vector<int> G[N];
int n,m;
int fa[N],ok,t;
bool vis[N];
void dfs(int x,int xfa,int &t)
{
	vis[x]=1;
	for(int y:G[x])if(y!=xfa)
	{
		int tt=t;
		if(vis[y])
		{
			ok=1;
			if(t==0)t=1;//当前联通块未返祖，否则不管这条边 
		}
		else
		{
			fa[y]=x;
			dfs(y,x,t);
		}
		if(tt!=t)fa[x]=y;//凡是进去前后t不一样的都要把边反向
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])//未走过 
		{
			ok=0;t=0;
			dfs(i,0,t);
			if(!ok) {printf("NIE\n"); return 0;} 
		}
	}
	printf("TAK\n");
	for(int i=1;i<=n;++i) printf("%d\n",fa[i]);
	return 0;
}