#include<cstdio>
#include<vector>
using namespace std;
#define IN(v) (v)
#define OUT(v) (v+n)
#define MAX_V 5000
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOREACH(it,V) for(typeof((V).begin()) it = (V).begin(); it!=(V).end(); ++it)
int V,V1;
vector<int> G[MAX_V];
int match[2*MAX_V];
int color[MAX_V];
bool TMatchDFS(int v){
color[v] = false;
FOREACH(it, G[v])
if(match[*it]==-1||color[match[*it]]&&TMatchDFS(match[*it])){
match[v] = *it;
match[*it] = v;
return true;
}
return false;
}
int TurboMatching(){
int k, res = 0;
REP(i,V) match[i] = -1;
do{
k = 0;
REP(i, V1) color[i] = true;
REP(i, V1)
if(match[i]==-1&&color[i]&&TMatchDFS(i)) ++k;
res += k;
} while(k!=0);
return res;
}
void readInput(){
int n, m, a, b;
scanf("%d%d", &n, &m);
V = 2*n;
V1 = n;
while(m--){
scanf("%d%d", &a, &b);
--a; --b;
G[IN(a)].push_back(OUT(b));
}
}
void cleanUp(){
REP(i, 2*n) G[i].clear();
}
int main()
{
int z, k;
scanf("%d", &z);
while(z--){
readInput();
k = TurboMatching();
if(k==n) printf("TAK\n");
else printf("NIE\n");
cleanUp();
}
return 0;
}