P5913 [POI 2004] KAG

题目描述

输入格式

第一行一个整数 $k$ 表示 $k$ 组数据。

接下来描述每个数据开头两个数 $n$ 和 $m$，接下来 $m$ 行每行两个数表示一条边。

输出格式

输出共 $k$ 行，每行输出一个判定，如果该图为 c-algae 输出 TAK，否则输出 NIE。

输入输出样例 #1

输入 #1

3
3 2
1 2
2 3
4 3
1 2
2 3
3 4
3 3
1 2
2 3
3 1

输出 #1

TAK
NIE
TAK

说明/提示

对于 $100\%$ 的数据，$1\le k\le10$，$1\le n\le10^4$，$0\le m\le10^5$。