题目描述

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

给定一棵树（即，一个无环的无向连通图），每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$，并把 $v$ 重新涂成和 $u$ 一样的颜色。

你的任务是确定经过一系列操作（有可能不进行任何操作）之后，一种最初的涂色情况能否变为最终给定的涂色情况。

输入格式

本题有多组测试数据。

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

第一行，一个整数 $n$，表示树的节点数；

第二行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则初始时第 $i$ 个节点被涂成红色。如果第 $i$ 个字符是 $1$，则初始时第 $i$ 个节点被涂成黑色；

第三行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则最后第 $i$ 个节点必须被涂成红色。如果第 $i$ 个字符是 $1$，则最后第 $i$ 个节点必须被涂成黑色；

接下来 $n - 1$ 行，其中第 $i$ 行有两个整数 $a_i, b_i$，表示树上的一条边；

输出格式

对于每组数据：

一行，一个字符串。如果存在一个操作序列能使涂色情况变为最终给定的情况，输出 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

提示

对于 $100\%$ 的数据，$1 \leq T, n \leq 10^5$，$1 \leq \sum n \leq 10^6$，$1 \leq a_i, b_i \leq n$。