ACM-ICPC-OJ训练营

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

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≤100

3≤N≤100

1≤Pi≤i

∑N≤6000

1847: Similarity

题目描述

输入描述

输出描述

样例输入

样例输出

来源