ДОРЕШИВАНИЕ 2014 ACM-ICPC Украина, 2ой Раунд Украина, Сентябрь 13
Ksyusha got a great present for her birthday - a "Permugame". Gear for "Permugame" consists of the two permutations of size n:
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.
In the first line you are given a single integer n (1 ≤ n ≤ 100000) - size of the board and permutations p and q. In the next line permutation
pi (1 ≤
pi ≤ n) is given as a list of integers separated by spaces. In the third line permutation
qi (1 ≤
qi ≤ n) is given in the same format. It is guaranteed that
pi ≠ i and
qi ≠ i for each i in [1, n].
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.
2 2 1 2 1
4 2 4 1 3 3 4 2 1
5 5 3 4 2 1 2 5 4 3 1