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

#3613. 「PA 2021」Drzewo czerwono-czarne

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2021 Runda 5 Drzewo czerwono-czarne

你熟悉红黑树这种数据结构吗？在本题我们将考虑一种节点颜色为红色或黑色的树，但请放心，如果你听说过刚才提到的数据结构的话，最好迅速忘掉它。

给定一棵树（即，一个无环的无向连通图），每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $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$ 个测试点中，存在一个操作序列能使涂色情况变为最终给定的情况，输出 TAK，否则输出 NIE。

样例

输入

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

输出

TAK
TAK
NIE

对于第一个测试点，我们可以让节点 $3$ 重新涂成节点 $2$ 的颜色，然后让节点 $4$ 重新涂成节点 $2$ 的颜色。这样，最后只剩下一个黑色节点，为节点 $1$。所以最后让节点 $2$ 重新涂为节点 $1$ 的颜色。在这三个操作之后，树的涂色情况与最终给定的情况相同。

对于第二个测试点，我们不需要进行任何操作——因为初始时颜色状态和最终给定的情况相同。

对于第三个测试点，两个节点的颜色不能原地交换。