这是一个晴朗的日子，在哥伦比亚大学的校园里，Alice 和 Bob 决定去 Butler 草坪玩他们最喜欢的游戏：排列游戏。因为天气太好了，Alice 想要在草坪上待得尽可能久，而 Bob 第二天有期中考试，想要回家复习。

排列游戏规则如下：

1. Alice 获得一个排列 $a$，Bob 获得一个排列 $b$，两者的长度均为 $n^*$。
2. Alice 选择一个下标 $i$（$1 \le i \le n$），并将她的棋子放在她的排列 $a$ 的位置 $i$ 上。
3. Bob 在看到 Alice 放置棋子的位置后，选择一个下标 $j$（$1 \le j \le n$），并将他自己的棋子放在他的排列 $b$ 的位置 $j$ 上。

4. Alice 和 Bob 每次各沿着自己的排列移动一步：

   • Alice 将她的棋子移动到下标 $a_i$，然后移动到 $a_{a_i}$，依此类推。
   • Bob 将他的棋子移动到下标 $b_j$，然后移动到 $b_{b_j}$，依此类推。

此过程将持续进行，直到在某一步后，两个棋子都回到了它们各自的初始下标。

Alice 想要最大化游戏进行的步数，而 Bob 想要最小化游戏进行的步数。假设两人都采取最优策略，游戏将进行多少步？

$^*$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。例如，$[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 不是排列（$2$ 在数组中出现了两次），$[1, 3, 4]$ 也不是排列（$n = 3$ 但数组中出现了 $4$）。

输入格式

第一行输入包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行输入包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$ — Alice 的排列 $a$。

第三行输入包含 $n$ 个互不相同的整数 $b_1, b_2, \dots, b_n$ — Bob 的排列 $b$。

输出格式

输出一个整数 — 假设两人都采取最优策略，游戏将进行的步数。

样例

输入样例 1

3
1 2 3
1 2 3

输出样例 1

1

输入样例 2

5
2 1 4 5 3
3 4 5 2 1

输出样例 2

3

输入样例 3

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

输出样例 3

5

说明

在第一个样例中，无论 Alice 和 Bob 初始将棋子放在哪个下标，游戏过程都只会持续 $1$ 步。

在第二个样例中，Alice 可以将她的棋子放在下标 $3$。Bob 在看到 Alice 放置棋子的位置后，将他的棋子放在下标 $1$。一步之后，Alice 的棋子将位于下标 $4$，Bob 的棋子将位于下标 $3$。两步之后，Alice 的棋子将位于下标 $5$，Bob 的棋子将位于下标 $5$。三步之后，Alice 的棋子回到了下标 $3$，而 Bob 的棋子回到了下标 $1$。