你熟悉红黑树这种数据结构吗？在这个问题中，我们将考虑带有红色或黑色顶点的树，但别担心——如果你听说过上述结构，最好尽快把它忘掉。

你被给定了一棵树（一个没有环的连通无向图），其中每个顶点都被涂成了红色或黑色两种颜色之一。你可以执行的操作是：选择两个由边连接的顶点 $v$ 和 $u$，并将 $v$ 的颜色重涂为 $u$ 的颜色。

你的任务是确定是否可以通过一系列（可能为空的）操作，从初始的颜色配置得到给定的最终颜色配置。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

接下来是各测试用例的描述。每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树中的顶点数。

下一行包含一个由 $n$ 个字符组成的字符串，每个字符为 0 或 1。如果第 $i$ 个字符为 0，则第 $i$ 个顶点初始被涂为红色。如果第 $i$ 个字符为 1，则第 $i$ 个顶点初始被涂为黑色。

下一行包含一个由 $n$ 个字符组成的字符串，每个字符为 0 或 1，以同样的方式描述了执行操作后每个顶点应为红色还是黑色（0 表示红色，1 表示黑色）。

接下来的 $n-1$ 行，每行包含两个整数。其中第 $j$ 行包含整数 $a_j$ 和 $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$)，表示顶点 $a_j$ 和 $b_j$ 之间有一条边。你可以假设给定的边序列描述了一棵合法的树。

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

输出应包含 $t$ 行。如果第 $k$ 个测试用例可以将树变为目标状态，则第 $k$ 行应输出单词 TAK。否则，应输出单词 NIE。

样例

输入 1

3
4
1011
1100
1 2
2 3
2 4
2
10
10
1 2
2
10
01
1 2

输出 1

TAK
TAK
NIE

说明

样例解释：在第一个测试用例中，我们可以先将第三个顶点重涂为第二个顶点的颜色，然后将第四个顶点重涂为第二个顶点的颜色。这样，剩下的最后一个黑色顶点就是第一个顶点。因此，现在只需将第二个顶点重涂为第一个顶点的颜色即可。经过这三次操作后，所有顶点的颜色都与给定的最终配置相符。

在第二个测试用例中，我们不需要执行任何操作——两个顶点初始时就已经具有正确的颜色。

在第三个测试用例中，无法交换顶点的颜色。