311271: CF1958I. Equal Trees

I. Equal Treestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two rooted trees, consisting of $n$ vertices each. The vertices in the trees are numbered from $1$ to $n$, and the root is the vertex $1$.

You can perform the following operation: choose the tree and the vertex $v$ (except the root of the tree) in it; connect the child nodes of $v$ to the parent of $v$ and remove $v$ from the tree.

Let's say that two trees are equal if both of the following conditions hold:

• the sets of remaining vertices in both trees are the same;
• for every vertex $v$ which is not deleted, its parent in the first tree is the same as its parent in the second tree.

Your task is to calculate the minimum number of aforementioned operation in order to make the trees equal.

Input

The first line contains a single integer $n$ ($2 \le n \le 40$) — the number of vertices in the trees.

The second line contains $n-1$ integers $a_2, a_3, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ the parent of the $i$-th vertex in the first tree. Vertex $1$ is the root.

The third line contains $n-1$ integers $b_2, b_3, \dots, b_n$ ($1 \le b_i \le n$), where $b_i$ the parent of the $i$-th vertex in the second tree. Vertex $1$ is the root.

Output

Print a single integer — the minimum number of aforementioned operation in order to make the trees equal.

ExamplesInput

5
1 5 5 1
1 4 1 2

Output

4

Input

2
1
1

Output

0

Input

10
4 7 10 6 2 9 7 1 1
1 2 10 3 4 6 6 5 5

Output

10

题目大意：
给定两棵由n个顶点组成的根树，顶点从1到n编号，根是顶点1。你可以执行以下操作：选择一棵树和其中的一个顶点v（不是根），将v的孩子节点连接到v的父节点，并从树中移除v。如果两棵树的剩余顶点集相同，并且对于未删除的每个顶点v，它在第一棵树中的父节点与它在第二棵树中的父节点相同，则称两棵树相等。任务是计算使两棵树相等所需的最小操作数。

输入数据格式：
第一行包含一个整数n（2≤n≤40）——树的顶点数。
第二行包含n-1个整数a2, a3, ..., an（1≤ai≤n），其中ai是第一棵树的第i个顶点的父节点。顶点1是根。
第三行包含n-1个整数b2, b3, ..., bn（1≤bi≤n），其中bi是第二棵树的第i个顶点的父节点。顶点1是根。

输出数据格式：
打印一个整数——使两棵树相等所需的最小操作数。

示例：
输入：
5
1 5 5 1
1 4 1 2
输出：
4

输入：
2
1
1
输出：
0

输入：
10
4 7 10 6 2 9 7 1 1
1 2 10 3 4 6 6 5 5
输出：
10题目大意： 给定两棵由n个顶点组成的根树，顶点从1到n编号，根是顶点1。你可以执行以下操作：选择一棵树和其中的一个顶点v（不是根），将v的孩子节点连接到v的父节点，并从树中移除v。如果两棵树的剩余顶点集相同，并且对于未删除的每个顶点v，它在第一棵树中的父节点与它在第二棵树中的父节点相同，则称两棵树相等。任务是计算使两棵树相等所需的最小操作数。 输入数据格式： 第一行包含一个整数n（2≤n≤40）——树的顶点数。 第二行包含n-1个整数a2, a3, ..., an（1≤ai≤n），其中ai是第一棵树的第i个顶点的父节点。顶点1是根。 第三行包含n-1个整数b2, b3, ..., bn（1≤bi≤n），其中bi是第二棵树的第i个顶点的父节点。顶点1是根。 输出数据格式： 打印一个整数——使两棵树相等所需的最小操作数。 示例： 输入： 5 1 5 5 1 1 4 1 2 输出： 4 输入： 2 1 1 输出： 0 输入： 10 4 7 10 6 2 9 7 1 1 1 2 10 3 4 6 6 5 5 输出： 10