Kotlin Heroes: Episode 10 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 10:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

graphs

meet-in-the-middle

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
I. Equal Trees

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

51 5 5 11 4 1 2

Output

4

Input

211

Output

0

Input

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

Output

10

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 11:22:29 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|