Competitions

# 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