“邪恶就是邪恶。无论大小、高低，皆无区别。程度是随意的，定义也是模糊的……但对于 Gebyte 来说并非如此。在长期宿醉的情况下，进行深入的道德反思并不容易，所以每当有两个人请求 Gebyte 杀死对方时，他眨眼间就知道哪种选择是“两害相权取其轻”。

作为一名强大的女巫，你可以预见 Gebyte 旅途中的遭遇：在接下来的 $k$ 天里，他每天都会遇到一对处于冲突中的人。你还能预见他在每次遭遇中会杀死哪个人。你决定利用这种洞察力为自己谋利：你希望确保你特别不喜欢的几个人最终成为受害者。

不幸的是，你的魔法不足以强迫 Gebyte 做出他认为“两害相权取其重”的决定。然而，你精通可以消除宿醉的咒语。如果你在某次遭遇前施展这种咒语，这位猎魔人——突然恢复了非凡的推理清晰度——将开始更深入地思考他所面临的困境，结果是不会杀死任何人。（不过，到了晚上，他肯定会去当地的小酒馆，所以第二天早上他又会回到通常宿醉的状态。）

你可以随意多次施展咒语。你能够确保你所有的敌人都死在 Gebyte 手中吗？

注意，一个人可以参与多次冲突。任何给定的遭遇只有在双方都还活着时才会发生——否则，那天什么也不会发生。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 1\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($2 \le n \le 10^6, 1 \le k \le 10^6$)，分别表示人数和 Gebyte 旅途中的会议次数。人员编号为 $1$ 到 $n$，会议编号为 $1$ 到 $k$。

接下来的 $k$ 行描述了这些会议。第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，意味着在第 $i$ 天，Gebyte 将遇到 $a_i$ 和 $b_i$ 之间的冲突，并且他会决定杀死 $b_i$ 是“两害相权取其轻”。

下一行包含一个整数 $s$ ($1 \le s \le n$)，即你的敌人数量。

测试用例的最后一行包含 $s$ 个不同的整数 $s_j$ ($1 \le s_j \le n$)，按升序排列。此列表中的所有人都必须死在 Gebyte 手中。所有其他人可以存活，也可以不存活。

所有测试用例中 $n$ 和 $k$ 的总和均不超过 $4\,000\,000$。

实现细节

如果 Gebyte 多次遇到同一对人，你不能假设他每次的选择都相同。也许在此期间他获得了新的信息，改变了他的判断。换句话说，可能存在 $\exists i, j (a_i = b_j \wedge a_j = b_i)$。

输出格式

对于每个测试用例，按以下格式打印解决方案。

如果存在解决方案，第一行输出单词 TAK。下一行输出一个由 $k$ 个字母 T 和 N 组成的字符串。如果你想在第 $i$ 天让 Gebyte 杀死 $b_i$，则序列的第 $i$ 个字母应为 T。另一方面，如果你想让 Gebyte 在第 $i$ 天不杀死任何人，则序列的第 $i$ 个字母应为 N。（如果在你的解决方案中，Gebyte 已经杀死了 $a_i$ 和/或 $b_i$，那么在第 $i$ 个位置打印 T 或 N 都没有关系——冲突将不会发生，Gebyte 当天也不会杀死任何人。）如果输入中列出的所有 $s$ 个敌人都没能存活到最后，你的解决方案将被接受。

如果没有正确的解决方案，则单行输出 NIE。

样例

输入 1

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

输出 1

TAK
NTTTNT
NIE

说明

在第一个测试用例中，如果我们允许 Gebyte 每次都选择“两害相权取其轻”，那么在第一天他会杀死 2 号，随后的冲突都不会发生。因此，1、3、4 和 5 号会存活。

另一方面，如果我们阻止 Gebyte 在第一天和第五天行动（即 NTTTNT 方案），那么 Gebyte 将在第二天杀死 1 号，第三天杀死 5 号，第四天杀死 3 号，第六天杀死 2 号。因此，只有 4 号会存活。另一个正确的解决方案是 NTNTNT，它让 4 号和 5 号存活。

在第二个测试用例中，不可能同时杀死 2 号和 3 号。