[AdditionalFile5682.zip](file://AdditionalFile5682.zip?type=additional_file)

#5682. 「PA 2026」Kampania wyborcza

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 3 Kampania wyborcza

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

各政党依次进行巡回访问，每个政党只进行一次访问，后一个政党的巡回访问只能在前一个政党的访问结束后开始。政党每经过一个城市，就会访问当地所有居民并说服他们投票给自己（例如，通过送他们一袋土豆）。所有被访问的居民都会被说服，但如果后来有另一个政党的代表访问了该城市（例如，邀请他们吃烤肉串），他们的立场就会改变。

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

Bajtoni 教授正在分析选举结果，并想知道这些结果是否可能是在符合规则的情况下产生的，还是明确表明了某个政党违反了规则或选举存在舞弊。请编写一个程序，帮助他判断每个省份的选举结果是否合法。

注意：教授不知道政党巡回访问的具体顺序，这个顺序不必与题目描述中的编号一致。

输入格式

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

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

下一行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(1 \leq a_{i} \leq k)$，其中 $a_{i}$ 表示在第 $i$ 个城市获胜的政党编号。

接下来的 $m$ 行描述了该省的道路：第 $i$ 行包含两个整数 $u_{i}, v_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq 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$，且省内任意两个城市之间均可通过现有道路到达。