Problem K
Tree Hopping

You are given a tree and a permutation of its vertices. It can be proven that for any tree and any pair of source/destination nodes, there is some permutation of the nodes where the first node is the source, the last node is the destination, and the distance between each pair of adjacent nodes in the permutation is less than or equal to three. Here the distance between two nodes $a$ and $b$ is the number of tree edges that must be traversed to get from $a$ to $b$.

Your job will be to write a verifier for this property. Given such a permutation and the tree, validate whether the distance between each pair of adjacent nodes in the permutation is less than or equal to three.

Input

The first line of input contains an integer $t$ ($1 \le t \le 50{,}000$), which is the number of test cases.

In each test case, the first line of input contains an integer $n$ ($2 \le n \le 100{,}000$), which is the number of nodes in the tree. The nodes are numbered from $1$ to $n$.

Each of the next $n-1$ lines contains a pair of integers $a$ and $b$ ($1 \le a < b \le n$), representing an edge in the tree between nodes $a$ and $b$.

Each of the next $n$ lines contains an integer $p$ ($1 \le p \le n$, all values distinct). This is the permutation of the nodes.

The sum of the values of $n$ over all test cases will not exceed $100{,}000$.

Output

For each test case, output a single line with a single integer, which is $1$ if the given permutation satisfies the constraint that every pair of adjacent nodes in the permutation has distance less than or equal to three in the tree. Output $0$ if the given permutation does not satisfy this constraint.

2
5
1 2
2 3
3 4
4 5
1
3
2
5
4
5
1 2
2 3
3 4
4 5
1
5
2
3
4

1
0