#include<bits/stdc++.h>
using namespace std;

constexpr int M=2e5+7;

vector<int>g[M];
int k[M];

void nie(){
	cout<<"NIE\n";
	exit(0);
}

void dfs(int v){
	for(auto w:g[v]){
		if(k[w]!=-1) continue;
		k[w]=k[v]^1;
		dfs(w);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m,a,b;
	cin>>n>>m;
	
	for(int i=1; i<=n; i++) k[i]=-1;
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++){
		if(g[i].empty()) nie();
		if(k[i]!=-1) continue;
		k[i]=0;
		dfs(i);
	}
	
	cout<<"TAK\n";
	for(int i=1; i<=n; i++) cout << ( k[i] ? "K\n" : "S\n" );
	
	return 0;
}