在 Bajtocja 举行了地方选举。每个省份都选出了自己的省长。每个省份都有若干个城市，城市之间由双向道路连接。作为竞选活动的一部分，在该省份活动的每个政党都会进行一次巡回访问，访问一定数量的城市。按照传统，政党从某个城市出发，经过若干次（可能是 0 次）移动到相邻的城市，最后在某个城市（可能是出发城市）结束。在此过程中，政党可能会多次经过同一个城市或同一条道路。

各政党按一定顺序进行巡回访问，每个政党只进行一次巡回，且下一个政党的巡回必须在前一个政党的巡回结束后才能开始。政党每经过一个城市，就会访问该城市的所有居民，并说服他们投票给自己（例如，通过给他们一袋土豆）。每个被访问的居民都会被说服，但如果后来有另一个政党的代表访问了该城市（例如，邀请他们去吃烤肉串），他们就会改变主意。

最初，没有任何居民被说服投票给任何人，但你可以假设每个城市至少被访问过一次，并且其居民最终被说服投票给其中一个政党。

Bajtoni 教授正在分析选举结果，并想知道这些结果是否可能是在符合所有规则的情况下通过竞选活动产生的，或者这些结果是否明确表明某个政党违反了规则，亦或是选举被操纵了。

请编写一个程序，帮助他回答每个省份的这个问题。

请注意，Bajtoni 教授不知道各政党进行巡回访问的顺序——特别是，这个顺序不一定与题目描述中的编号一致。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示 Bajtocja 的省份数量。

接下来是各省份的描述。每个省份描述的第一行包含三个整数 $n, m, k$ ($1 \le n, m, k \le 10^5$)，分别表示城市数量、道路数量以及在该省份活动的政党数量。

下一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le k$)，其中 $a_i$ 表示在第 $i$ 个城市获胜的政党编号。

接下来的 $m$ 行包含省份内道路的描述：第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示城市 $u_i$ 和 $v_i$ 之间的双向道路。每对城市之间最多存在一条道路。

所有省份的城市总数、所有道路总数以及所有政党总数均不超过 $10^5$。

输出格式

输出 $t$ 行；第 $i$ 行应包含一个单词 TAK（如果第 $i$ 个省份的选举结果可能是由竞选活动产生的），否则输出 NIE。

样例

样例输入 1

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

样例输出 1

TAK
TAK
NIE

说明

在第一个省份中，一种可能的方案是：首先政党 1 访问了所有城市，然后政党 2 仅访问了 2 号城市，最后政党 3 仅访问了 5 号城市。

在第二个省份中，一种可能的方案是：首先政党 1 和 3 访问了某些城市集合，然后政党 2 访问了所有城市。

在第三个省份中，无论哪个政党先进行竞选活动，都不可能得到给定的选举结果。

子任务

在至少一组测试中，所有省份都满足 $m = n - 1$ 且省份内的任意两个城市之间均可通过现有道路到达。