J. Permutation Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It is a sunny day on Columbia campus, and Alice and Bob decide to go to Butler Lawns to play their favorite game: Permutation Game. Since the weather is so nice, Alice wants to stay on the lawns as long as possible, while Bob has a midterm the next day and wants to get home to study.

Permutation Game is played as follows:

  1. Alice receives a permutation $$$a$$$ and Bob receives a permutation $$$b$$$, both of size $$$n$$$$$$^{\text{∗}}$$$.
  2. Alice chooses an index $$$i$$$ ($$$1 \leq i \leq n$$$) and places a token on position $$$i$$$ of her permutation $$$a$$$.
  3. Bob, after seeing where Alice has placed her token, chooses an index $$$j$$$ ($$$1 \leq j \leq n$$$) and places his own token on position $$$j$$$ of his permutation $$$b$$$.
  4. Alice and Bob each follow their permutation one step at a time:
    • Alice moves her token to index $$$a_i$$$, then $$$a_{a_i}$$$, and so on.
    • Bob moves his token to index $$$b_j$$$, then $$$b_{b_j}$$$, and so on.
    This process continues until both tokens return to their respective starting indices after a step is performed.
Alice wants to maximize the number of steps performed, while Bob wants to minimize the number of steps performed. Assuming both players play optimally, how many steps will be performed?

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, [$$$2$$$, $$$3$$$, $$$1$$$, $$$5$$$, $$$4$$$] is a permutation, but [$$$1$$$, $$$2$$$, $$$2$$$] is not a permutation ($$$2$$$ appears twice in the array), and [$$$1$$$, $$$3$$$, $$$4$$$] is also not a permutation ($$$n = 3$$$ but there is a $$$4$$$ in the array).

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The second line of input contains $$$n$$$ distinct integers $$$a_1, a_2, ..., a_n$$$ — Alice's permutation $$$a$$$.

The third line of input contains $$$n$$$ distinct integers $$$b_1, b_2, ...,b_n$$$ — Bob's permutation $$$b$$$.

Output

Output a single integer — the number of steps that will be performed in the game, assuming both players play optimally.

Examples
Input
3
1 2 3
1 2 3
Output
1
Input
5
2 1 4 5 3
3 4 5 2 1
Output
3
Input
10
2 8 1 5 4 7 6 10 9 3
7 3 9 10 2 1 6 8 4 5
Output
5
Note

In the first sample, regardless of which indices Alice and Bob place their tokens on to start, the process will last for just one step.

In the second example, Alice may place her token at index $$$3$$$, and Bob, seeing where Alice has placed her token, places his at index $$$1$$$. After one step, Alice's token will be at index $$$4$$$ and Bob's will be at index $$$3$$$. After two steps, Alice's token will be at index $$$5$$$ and Bob's will be at $$$5$$$. And after three steps, Alice's token returns to index $$$3$$$, while Bob's returns to index $$$1$$$.