题目描述

在巴伊托奇亚举行了地方选举。$t$ 个省份各自选出了自己的省长。每个省份有若干座城市，通过双向道路相互连接。在竞选活动中，每个活跃于该省的政党在巡回期间访问了若干座城市。按照惯例，政党从某座城市出发，经过若干次（可能为 $0$ 次）沿道路前往相邻城市后，在某座（可能是同一座）城市结束行程，过程中可能多次经过同一座城市或同一条道路。

各政党按某一顺序进行了巡回，其中每个政党只进行一次巡回，且下一个政党的巡回须在上一个政党的巡回结束后方可开始。在某政党所经过的城市中，该政党拜访了所有居民，并说服他们投票给自己（例如，带去了一袋土豆）。每位被拜访的居民都被说服了，但如果之后另一个政党的代表拜访了他（例如，邀请他吃烤肉串），他便会改变主意。

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

巴伊托尼教授正在分析选举结果，他想知道：这样的结果是否有可能在完全遵守所有规则的竞选活动后产生，还是说这些结果明确表明某个政党违反了规则，或者选举遭到了舞弊。

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

请注意，巴伊托尼教授不知道各政党进行巡回的顺序——特别是，这一顺序不必与题目中的编号顺序一致。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示巴伊托奇亚的省份数量。

接下来的若干行是对各省份的描述。每个省份描述的第一行包含三个整数 $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 \ne v_i$），表示城市 $u_i$ 与城市 $v_i$ 之间有一条双向道路。每对城市之间最多存在一条道路。

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

输出格式

输出应包含 $t$ 行；若第 $i$ 个省份的选举结果有可能由合规的竞选活动产生，则第 $i$ 行输出单词 TAK，否则输出 NIE。

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

TAK
TAK
NIE

提示

样例说明

在第一个省份中，存在这样一种可能的场景：首先政党 $1$ 访问了所有城市，然后政党 $2$ 仅访问了第 $2$ 号城市，之后政党 $3$ 仅访问了第 $5$ 号城市。

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

对于第三个省份，无论哪个政党最先进行竞选活动，都不可能得到题目所给出的选举结果。

评分

在大于零分的子任务中，所有省份均满足 $m = n - 1$ 的条件，且在同一省份内每对城市之间均可通过现有道路互相到达。