#include<bits/stdc++.h>
using namespace std;
int n,m,a[200001],h[200001],h1[200001];
vector<int>q[200001];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		q[x].push_back(y);
		q[y].push_back(x);
	}
	int ans=1;
//	h[1]=1;h1[1]=1;a[1]=1;
	for(int j=1;j<=n;j++)
	{
		for(int i=0;i<q[j].size();i++)
		{
			if(!a[j])a[j]=1;
			if(!a[q[j][i]])
			{
				a[q[j][i]]=a[j]%2+1;
//				cout<<q[j][i]<<endl;
			}
		}
	}
//	dfs(1,1,2);
	for(int i=1;i<=n;i++)
	{
		if(!a[i])
		{
			printf("NIE");
			return 0;
		}
	}
	printf("TAK\n");
	for(int i=1;i<=n;i++)
	{
		if(a[i]==1)printf("K\n");
		else if(a[i]==2)printf("S\n");
		else cout<<endl;
	}
	return 0;
}