题目描述

题目译自 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