eolymp
Competitions

ДОРЕШИВАНИЕ 2014 ACM-ICPC Украина, 2ой Раунд Украина, Сентябрь 13

Permugame

Ksyusha got a great present for her birthday - a "Permugame". Gear for "Permugame" consists of the two permutations of size n: pi, qi and a square board n * n cells. According to the rules cells (i, j) and (a, b) are connected to each other by a tunnel if and only if either (a = i and b = Pj) or (a = Pi and b = j). The only goal of the game is to find such a minimal integer k (k > 0), that every cell of the board can be painted in one of the k colors. The only restriction is that any two connected cells should have different colors. Ksyusha is too lazy to play "Permugame" so she asked you to figure out the answer.

Input

In the first line you are given a single integer n (1n100000) - size of the board and permutations p and q. In the next line permutation pi (1pin) is given as a list of integers separated by spaces. In the third line permutation qi (1qin) is given in the same format. It is guaranteed that pii and qii for each i in [1, n].

Output

Print the minimal integer k (k > 0) such that every cell of the n * n board can be painted in one of the k colors.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
2 1
2 1
Output example #1
2
Input example #2
4
2 4 1 3
3 4 2 1
Output example #2
2
Input example #3
5
5 3 4 2 1
2 5 4 3 1
Output example #3
3
Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem A