|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||36||21||21||60.000%|
A matryoshka doll is a set of wooden figurines of increasing sizes that can be nested one inside the other. They are nested by placing a figurine inside a larger figurine which is, in turn, placed inside a yet larger figurine, etc. We may never place more than one figurine directly inside another figurine, no matter the sizes of the figurines involved.
We are currently playing with a set of n figurines denoted by integers 1 through n in the order of increasing size. If a figurine a is placed directly inside a figurine b we say that b is a parent of a, and if a figurine has no parent we call it free. A configuration of the whole set can be described by specifying the current parent of each figurine.
We are allowed to perform the following steps while playing:
Find the minimal number of steps to obtain the given target configuration from the given initial configuration.
The first line contains an integer n (1 ≤ n ≤ 100 000) — the number of figurines.
The following line contains a sequence of n integers p1, p2, . . . , pn (0 ≤ pk ≤ n) describing the initial configuration. The k-th integer pk is 0 if the figurine k is free, or the parent of figurine k otherwise.
The following line contains a sequence of n integers q1, q2, . . . , qn (0 ≤ qk ≤ n) describing the target configuration in the same format.
You may assume that both configurations are valid: a figurine is always smaller than its parent and no two figurines have the same parent.
Output a single integer — the minimal number of steps.
7 3 5 4 0 7 0 0 3 5 0 6 7 0 0
6 2 5 4 0 0 0 2 6 4 5 0 0