C-algae 是 Byteotians 最喜爱的民族菜肴。C-algae 具有非常特殊的结构。由单个细胞组成的藻类即为 c-algae。两个 c-algae $K_1$ 和 $K_2$ 可以通过以下两种方式之一组合：

• 选择 $K_1$ 和 $K_2$ 的所有细胞，以及 $K_1$ 和 $K_2$ 的所有连接，
• 选择 $K_1$ 和 $K_2$ 的所有细胞，以及 $K_1$ 和 $K_2$ 的所有连接，并建立额外的连接：$K_1$ 中的每个细胞都与 $K_2$ 中的每个细胞相连。

由此我们得到一个新的 c-algae $K$。

不幸的是，敌对国家 Bitotia 最近开始销售模仿 c-algae 的藻类。它们看起来非常相似，以至于很难区分伪造品和真正的 c-algae。这就是 Byteotian 政府要求你编写一个程序来验证给定的藻类是否为 c-algae 的原因。

任务

编写一个程序，完成以下工作：

• 从标准输入读取藻类的描述，
• 检查其中哪些是真正的 c-algae，
• 将答案写入标准输出。

输入格式

标准输入的第一行包含一个整数 $k$ ($1 \le k \le 10$)，表示需要检查的藻类数量。接下来的行中包含 $k$ 个藻类的描述。每个描述的形式如下：第一行包含两个用空格分隔的整数 $n$ 和 $m$ ($1 \le n \le 10\,000$, $0 \le m \le 100\,000$)，分别表示细胞的数量和连接的数量。细胞编号从 $1$ 到 $n$。在接下来的 $m$ 行中，描述了连接情况——每行包含两个用空格分隔的整数 $a$ 和 $b$ ($a\ne b$, $1 \le a,b \le n$)，表示细胞 $a$ 和 $b$ 相连。每个连接仅被指定一次。

输出格式

应向标准输出写入 $k$ 行。第 $i$ 行应写入一个单词：

• TAK - （即波兰语中的“是”）- 如果第 $i$ 个藻类是真正的 c-algae，
• NIE - （即波兰语中的“否”）- 否则。

样例

输入 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