Given two rooted trees , . Let represent the number of nodes in tree , then the two trees satisfy the following constraints: . It guarantees that is a small constant. You can delete several nodes in , assuming that the subgraph obtained after deleting the nodes is . He wants to know if there is a way to delete nodes such that the subgraph obtained after deletion satisfies the following conditions:
- is connected.
- contains the root node in (that is, the root node is not deleted during deletion).
- and are isomorphic (that is, there is a way to relabel the points in , so that the graph obtained by relabeling is exactly the same as , and the root node in is exactly the root of after relabeling the nodes).
Input format
There are multiple sets of test data for this question. The first line of input contains two positive integers , and a non-negative integer . The three numbers represent the current test point number, the number of test data groups and the constant given in the question. if the current test data is a sample. It is guaranteed that , .
For each set of test data: The first line of input contains a positive integer , representing the number of nodes in tree , guaranteeing , and . The second line of input contains integers describing the structure of the tree . Specifically, the ()-th integer represents the parent node of node in tree , and if it is the root node, . It is guaranteed that the tree obtained according to the above rules is a connected rooted tree. The third line of input contains a positive integer , representing the number of nodes in , which is guaranteed to satisfy for all test data. The fourth line of input contains integers describing the structure of the tree . Specifically, the () integer represents the parent node of node in tree , and if it is the root node, . It is guaranteed that the tree obtained according to the above rules is a connected rooted tree.
Output format
For each set of test data:
Output one string per line. If there is a way to delete the node in so that it can satisfy the above three conditions at the same time, output Yes
; otherwise, output No
.
Samples
Sample inputs and outputs can be found here.
Sample Input 1
0 3 1
3
2 ‐1 2
2
‐1 1
4
3 3 ‐1 3
3
2 3 ‐1
5
‐1 1 5 5 1
5
2 3 ‐1 3
Sample Output 1
Yes
No
Yes
Explanation of Sample 1
For the first test point, we delete node 1 of the first tree. At this point the remaining tree and the input second tree are both rooted trees with two nodes, so the output is Yes.
For the second test point, enter a depth of 1 for the first tree, but a depth of 2 for the second tree. Therefore, deleting the node of the first tree will not cause its tree height to increase to 2, so the output is No.
For the third test point, the input two trees are isomorphic to the tree in the figure below, so the output is Yes.
Sample 2
See iso/iso2.in and iso/iso2.ans in the player directory. The sample data range satisfies test points 7 ∼ 8
Sample 3
See iso/iso3.in and iso/iso3.ans in the player directory. The sample data range satisfies test points 9 ∼ 10.
Sample 4
See iso/iso4.in and iso/iso4.ans in the player directory. The sample data range meets test point 13.
Subtasks
For all test data, , , , . Additional restrictions for each test point are shown in the table below:
, | Case | Special Property | |||
---|---|---|---|---|---|
1,2,3 | None | ||||
4, 5, 6 | |||||
7, 8 | |||||
9, 10 | |||||
11 | |||||
12 | |||||
13 | |||||
14, 15, 16 | A | ||||
17, 18, 19, 20 | B | ||||
21 | None | ||||
22, 23 | |||||
24, 25 |
The special properties among the additional restrictions are as follows:
- Special property A: It is guaranteed that each node of the rooted tree is either a leaf node or has exactly 1 child node; another equivalent expression is that the rooted tree constitutes a chain, and the root node is a chain an endpoint.
- Special property B: It is guaranteed that each node of the rooted tree is either a leaf node or has exactly 2 child nodes, and each leaf node of is guaranteed to have the same depth; another equivalent expression is a rooted tree constitutes a complete binary tree, and the root node is the root node of the complete binary tree
Hint
The data does not have any targeted structure for any reasonable hash algorithm, so within a reasonable range, there is no need to worry too much about the loss of points due to hash collisions.
Comments