L. Label Matching
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Panda has a rooted tree with $$$n$$$ nodes, where node $$$1$$$ is the root. Each node $$$i$$$ in the tree has two labels: $$$a_i$$$ and $$$b_i$$$. Some of these values are designated as wildcards, which is represented by $$$0$$$. Specifically, two values $$$x$$$ and $$$y$$$ are considered equal if $$$x=y$$$ or if at least one of them is a wildcard $$$0$$$.

For a node $$$i$$$, let $$$T_i$$$ denote the subtree rooted at node $$$i$$$, which consists of node $$$i$$$ itself and all of its descendants in the tree. For each node $$$i$$$ from $$$1$$$ to $$$n$$$, Panda asks you the following question, and you must answer each one independently:

  • You can perform any number of swap operations (including zero). In each operation, you can choose any two nodes $$$u$$$ and $$$v$$$ within the subtree $$$T_i$$$ and swap $$$a_u$$$ and $$$a_v$$$. Determine whether it is possible, using some sequence of swaps, to make $$$a_k$$$ equal to $$$b_k$$$ for all nodes $$$k$$$ in the subtree $$$T_i$$$.

Note that each query is independent. The swaps you consider are only for that specific query and do not affect the initial state of the tree for subsequent queries.

Input

The first line contains a single integer $$$T$$$ ($$$1\le T\le 2\times 10^5$$$), representing the number of test cases.

For each test case the first line contains a positive integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), indicating the number of nodes.

The second line contains $$$n$$$ integers, the $$$i$$$-th of which is $$$a_i$$$ ($$$0\le a_i\le n$$$). If $$$a_i=0$$$, it represents a wildcard.

The third line contains $$$n$$$ integers, the $$$i$$$-th of which is $$$b_i$$$ ($$$0\le b_i\le n$$$). If $$$b_i=0$$$, it represents a wildcard.

The next $$$n - 1$$$ lines describe the structure of the tree. Each line contains two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$), representing an edge between node $$$u$$$ and node $$$v$$$. It is guaranteed that the given $$$n-1$$$ edges form a tree.

The sum of $$$n$$$ over all test cases is guaranteed to not exceed $$$2\cdot 10^5$$$.

Output

For each test case, you must print a single line with a binary string $$$s$$$ of length $$$n$$$. The $$$i$$$-th character of the string, $$$s_i$$$, should be $$$1$$$ if a valid swap scheme exists for the subtree $$$T_i$$$, and $$$0$$$ otherwise.

Example
Input
3
6
1 5 0 3 4 0
0 3 4 5 2 0
1 2
2 3
2 4
1 5
5 6
5
2 2 3 0 4
4 1 4 2 0
1 2
2 3
3 4
4 5
3
1 2 3
3 2 1
1 2
2 3
Output
111011
01111
100