Johnny 是第一个社交网络的创始人，但几乎没人知道这一点。这是因为当他忙于寻找代码中的那个 bug 时，他在项目组的同事卑劣地接管了公司并解雇了 Johnny。Johnny 决定利用他没能修复的那个 bug 进行报复：他可以对用户的一个子集 $X$ 进行“翻转”（flip）。翻转 $X$ 会改变 $X$ 中所有用户对之间的好友关系，即如果 $a$ 和 $b$ ($a, b \in X$) 原本是好友，翻转后他们将不再是好友，反之亦然。Johnny 认为，一旦所有翻转完成，失去所有好友的用户就会删除他们的账户，如果很多人这样做，被窃取的项目肯定会倒闭。Johnny 整晚都在寻找一个好的翻转序列，最终他想出了一系列用户子集 $V_1, V_2, \dots, V_k$。在他最终去睡觉之前，他确信他找到的这个序列会让所有用户删除他们的账户，但今天早上他不再那么确定了。考虑到睡眠不足、对同事的愤怒以及他那令人怀疑的编程能力，他可能犯了一个错误。这就是为什么你需要验证对于每个用户，在 Johnny 建议的翻转操作之后，该用户是否会没有好友。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n \le 2.5 \cdot 10^5, 1 \le k \le 10^4, 0 \le m \le \min\{\frac{n(n-1)}{2}, 2 \cdot 10^6\}$)，用空格分隔。它们分别表示：社交网络中的用户数量、网络中的好友对数量以及 Johnny 建议的操作序列长度。

接下来的 $m$ 行包含整数对 $a_i, b_i$，指定了互为好友的用户标识符 ($1 \le a_i, b_i \le n, a_i \neq b_i$)；这些数字由单个空格分隔。（无序的）好友对是唯一的。

接下来的 $k$ 行描述了集合 $V_i$。每一行包含一个整数序列 $s_i, v_{i,1}, \dots, v_{i,s_i}$，用空格分隔，其中 $s_i$ ($1 \le s_i \le n$) 是 $V_i$ 的大小，$v_{i,j}$ 是其中的元素。

$s_i$ 的总和不超过 $10^6$。

输出格式

输出应包含 $n$ 行：第 $i$ 行应包含单词 TAK（如果 Johnny 建议的翻转序列后第 $i$ 个用户没有好友），否则输出 NIE。

样例

样例输入 1

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

样例输出 1

TAK
TAK
TAK

样例输入 2

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

样例输出 2

TAK
NIE
TAK
NIE