405046: GYM101754 E Bonsai

Vasily likes bonsasi — the art of growing decorative trees. He has two beatiful trees, but his aesthetical sense tells him that these trees should be made as similar as possible.

Consider the task formally. Let us represent each tree with a connected graph without cycles with a specified root vertex. Vertices of both trees are numbered starting from one, and the root of each tree has number 1 among the vertices of this tree. Let us direct all edges away from the root of the tree. All edges starting at the same vertex are ordered (from left to right when looking at the tree from the front) by increasing of the index of vertices where the edges are directed to.

Vasily can perform two kinds of operation with either of the trees:

• Cut a leaf vertex from any tree, that is, a vertex without outgoing edges. The root of the tree can not be cut.
• Take two neighboring edges leaving the same vertex, and carefully tie them together with a piece of string. The ends of these edges effectively become one vertex, and all edges previously leaving the ends of the tied edges now leave this vertex instead. The order of the edges leaving the new vertex is defined as follows: all edges leaving the end of the left edge, followed by all edges leaving the end of the right edge. The relative order of edges in both lists is unchanged. Two edges that were tied are now considered as a single edge and two vertices are considered as a single vertex, thus they can be a part of a leaf cut or tie operation during next steps.

Vasily thinks that the trees have become equal if it is possible to put vertices, as well as edges of both trees in one-to-one correspondence so that:

• For any pair of corresponding vertices the number of edges leaving these vertices is the same, and all this edges are pairwise corresponding with respect to their order.
• The ends of corresponding edges are corresponding as well.

In particular, it follows from the rules that the roots of the trees must be corresponding.

Of course, Vasily doesn't want to ruin his trees too much. What is the smallest number of operations needed to make the trees equal?

The first line contains an integer n — the number of vertices of the first tree (1 ≤ n ≤ 5000).

The second line contains integers p₂, ..., p_n (1 ≤ p_i < i). Here, the number p_i is the number of the parent vertex of a non-root vertex i — the start vertex of the unique edge entering i.

The third line contains an integer m — the number of vertices of the second tree (1 ≤ m ≤ 5000).

The fourth line describes the parents of vertices 2, ..., m of the second tree in the same format as described above.

Print one number — the smallest number of operations needed to make the trees equal.

3
1 1
3
1 2

2

7
1 1 2 2 3 3
7
1 1 2 3 2 3

0

1
 
5
1 2 1 4

4

In the first sample it is possible to reach the goal in two operations: for example, we can cut the leaf vertex 3 of the first tree, and tie the edges (1, 2) and (1, 3) in the second tree.

In the second sample the trees are already equal regardless of the fact that the leaves are numbered differently.

In the third sample we have to successively cut all vertices of the second tree except for the root. Note that if a tree has only one vertex, the second line of its description is empty.