题目描述
题目译自 $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$ 个字符，每个字符是 $\texttt{0}$ 或 $\texttt{1}$ 中的一种。如果第 $i$ 个字符是 $\texttt{0}$，则初始时第 $i$ 个节点被涂成红色；如果是 $\texttt{1}$，则初始时第 $i$ 个节点被涂成黑色
• 接下来一行包含 $n$ 个字符，每个字符是 $\texttt{0}$ 或 $\texttt{1}$ 中的一种。表示操作结束后每个节点应被涂成的颜色。仍然 $\texttt{0}$ 表示红色，$\texttt{1}$ 表示黑色
• 接下来 $n-1$ 行，每行包含两个整数 $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$ 的颜色。在这三个操作之后，树的涂色情况与最终给定的情况相同。

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

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