덱 섞기

Alice와 Bob은 Don'tminion이라는 게임을 즐긴다. 이 게임에서는 크기가 각기 다른 덱을 여러 번 섞어야 한다. 자주 게임을 하다 보니 두 사람은 섞는 속도가 빠를 뿐만 아니라 섞는 방식도 항상 일정하다. Alice가 덱을 섞을 때마다 카드의 순열은 매번 같은 방식으로 바뀌고, Bob도 마찬가지로 덱을 섞을 때마다 항상 같은 순열을 적용한다. 게임을 하기에는 좋지 않은 성질이지만, 흥미로운 질문이 하나 떠오른다.

두 사람이 번갈아 덱을 섞으면 언젠가는 덱이 처음 상태와 같은 순서로 돌아온다는 것을 알고 있다. Alice가 먼저 한 번 섞고, 그다음 Bob이 한 번 섞고, 다시 Alice가 섞는 식으로 진행한다. 처음에는 정렬된 덱에서 시작한다. 하지만 두 사람은 덱이 다시 정렬되기까지 몇 번을 섞어야 하는지는 모른다.

몇 번 섞어야 하는지 계산할 수 있겠는가? Alice와 Bob은 주어진 시간 동안 많아야 10^12번까지 섞을 수 있으므로, 이보다 큰 수는 huge로 출력해야 한다.

• 첫째 줄에 정수 1 ≤ n ≤ 10^5이 주어진다. n은 덱에 있는 카드의 수이다.
• 둘째 줄에 n개의 서로 다른 정수 1 ≤ a1, a2, ..., an ≤ n이 주어진다. ai는 Alice가 덱을 섞었을 때, 이전에 i번 위치에 있던 카드가 이동하는 새 위치이다.
• 셋째 줄에 n개의 서로 다른 정수 1 ≤ b1, b2, ..., bn ≤ n이 주어진다. bi는 Bob이 덱을 섞었을 때, 이전에 i번 위치에 있던 카드가 이동하는 새 위치이다.

• 덱을 정렬하는 데 필요한 최소 섞기 횟수인 양의 정수 m > 0을 출력한다. 이 수가 10^12보다 크면 huge를 출력한다.