Similarity

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

There is a tree grows on both HNN and HBB's head. The two tree has the same size n and index start from 1.
As HBB's son, HNN suddenly realizes that his tree doesn't look like daddy's at all. So he can't stop crying and thinking about how hard the life is. So HBB has to remark son's tree to make it look like daddy's tree as much as possible.
We define the similarity degree of two tree's as the number of nodes whose farther has the same id in both tree. Note that root doesn't has farther node, so it can't increase the similarity degree.We define the similarity degree of two tree's as the number of nodes whose farther has the same id in both tree. For example, if node-2's farther node is node-3 in the first tree, and node-2's farther node is also node-3 in the second tree, then node-2 is such the kind of node which increase the similarity degree between the two tree.
It is a hard work to make HBB and HNN's similarity degree reach n-1(it is impossible to reach n because the root node), so if HBB can make their similarity degree reach n-3 or more, HNN will stop crying. Is it possible?

NOTE:maybe the similarity degree has already reach n-3 or more at the beginning, the answer is true of course

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer N: the size of the tree.
The next line gives the information of HNN's tree, the line contains N-1 numbers, the i-th number Pi gives the farther node of the node i+1.
The next line gives the information of HBB's tree, the input way is the same as HNN's tree.

Limits
$T \leq 100$
$3 \leq N \leq 100$
$1 \leq Pi \leq i$
$\sum N \leq 6000$

Output

For each test case output one line denotes the answer.
If the similarity can reach n-3, output "YES" , "NO" otherwise.

Sample Input

1 5 1 1 3 3 1 2 1 4

Sample Output

YES

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码