Problem Description

Are you familiar with the data structure called a red-black tree? In this problem, we will consider a tree whose nodes are colored red or black, but rest assured: if you have heard of the data structure mentioned above, it is best to forget it quickly.

You are given a tree (that is, a connected undirected graph with no cycles), where each node is colored either red or black. You may choose two adjacent nodes $v$ and $u$ (connected by an edge), and recolor $v$ to have the same color as $u$.

Your task is to determine whether, after a sequence of operations (possibly performing no operations at all), an initial coloring can be transformed into the given final coloring.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains an integer $n$, the number of nodes in the tree.

The second line contains $n$ characters, each being 0 or 1. If the $i$-th character is 0, then initially the $i$-th node is colored red. If the $i$-th character is 1, then initially the $i$-th node is colored black.

The third line contains $n$ characters, each being 0 or 1. If the $i$-th character is 0, then in the end the $i$-th node must be colored red. If the $i$-th character is 1, then in the end the $i$-th node must be colored black.

The next $n - 1$ lines each contain two integers $a_i, b_i$, describing an edge in the tree.

Output Format

For each test case:

Output one line with a string. If there exists a sequence of operations that transforms the coloring into the given final coloring, output TAK; otherwise output NIE.

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

TAK
TAK
NIE

Hint

Constraints: For $100\%$ of the testdata, $1 \leq T, n \leq 10^5$, $1 \leq \sum n \leq 10^6$, $1 \leq a_i, b_i \leq n$.

Translated by ChatGPT 5