#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

bool tak;

void BFS(int n,vector<int> G[], int kolor[]){
    tak=true;
	queue<int> Q;
	kolor[n]=1;
	Q.push(n);
	while(!Q.empty()){
	int k=Q.front();Q.pop();
	for(int i=0;i<(int)G[k].size();i++)
		if(kolor[G[k][i]]==0){
			kolor[G[k][i]]=(-1)*kolor[k];
			Q.push(G[k][i]);
		}else if(kolor[G[k][i]]==kolor[k]){
			cout<<"NIE"<<endl;
			tak=false;
			return;
		}
	}
}

int main()
{
	int z;
	cin>>z;
	for(int j=1;j<=z;j++)
    {
        vector<int> G[10001];
        int N,V;
        int kolor[10001]={0};

        cin>>N>>V;
        int k,l;
        for(int i=1;i<=V;i++){
            cin>>k>>l;
            G[k].push_back(l);
            G[l].push_back(k);
        }
        for(int n=1;n<=N;n++)
        {
            if(kolor[n]==0)BFS(n,G,kolor);
            if(!tak) break;
        }

        if(tak) cout<<"TAK"<<endl;
    }

	return 0;
}
