邪恶的巫师 Voldebyte 将勇敢的骑士 Bytter the Bold 囚禁在他的塔中。按照惯例，Voldebyte 承诺只要 Bytter 能解开他的一道（尚未解决的）谜题，就放他自由。不幸的是，Bytter 杀死了 Voldebyte 的宠物龙，并且差点杀死了 Voldebyte 本人，因此 Voldebyte 决定出一道非常困难的谜题。这是 Voldebyte 向 Bytter 提出的谜题：

Byteland 被划分为 $k$ 个县，总共有 $n$ 个城镇。此外，一些城镇对之间由双向道路连接。我想在每个县中选择一个城镇作为其首府，使得对于每一条道路，至少有一个端点是首府城镇。这可能吗？

请帮助可怜的 Bytter 自救，并为他解开这个谜题。

输入格式

标准输入的第一行包含三个整数：$n$ ($1 \le n \le 1\,000\,000$)，表示 Voldebyte 谜题中的城镇数量；$m$ ($0 \le m \le 1\,000\,000$)，表示道路数量；$k$ ($1 \le k \le n$)，表示县的数量。城镇编号从 $1$ 到 $n$。

接下来的 $m$ 行包含 $m$ 对整数 $a_{i}, b_{i}$ ($1 \le a_{i}, b_{i} \le n$, $a_{i} \neq b_{i}$)，第 $i$ 对表示连接城镇 $a_{i}$ 和 $b_{i}$ 的道路。任意两个城镇之间最多只有一条道路。

接下来的 $k$ 行描述了各个县。第 $j$ 行以一个整数 $w_{j}$ ($1 \le w_{j} \le n$) 开头，表示第 $j$ 个县中的城镇数量。随后是 $w_{j}$ 个整数，表示第 $j$ 个县中各城镇的编号（互不相同）。所有 $w_{j}$ 的总和等于 $n$。

输出格式

如果谜题无解，程序应在标准输出中输出一行单词 NIE（波兰语中的“不”）。

否则，程序应输出两行。第一行应包含单词 TAK（波兰语中的“是”），第二行应描述解法。第二行应包含恰好 $k$ 个整数。其中第 $i$ 个整数应为选定作为第 $i$ 个县首府的城镇编号。

如果存在多个正确的解，输出其中任意一个即可。

样例

样例输入 1

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

样例输出 1

TAK
2 1

样例输入 2

3 3 1
1 2
2 3
3 1
3 1 2 3

样例输出 2

NIE