카드 셔플

문제

3명의 플레이어(0, 1, 2)가 카드 게임을 한다. N장의 카드(0 ~ N-1번)를 사용하며, N은 3의 배수이다.

카드를 섞는 방법은 길이 N의 수열 S로 정의된다. 셔플을 한 번 하면 i번 위치의 카드가 S[i]번 위치로 이동한다. 카드 분배는 순서대로 이루어지며, 0번 위치는 플레이어 0, 1번 위치는 플레이어 1, 2번 위치는 플레이어 2, 3번 위치는 플레이어 0, ...와 같이 번갈아 가며 담당한다. 즉, 위치 j의 카드는 플레이어 (j mod 3)에게 배분된다.

각 카드가 최종적으로 어느 플레이어에게 가야 하는지는 길이 N의 수열 P로 주어진다. 처음에 i번 위치의 카드 번호는 i이다. 목표 상태는 i번 위치의 카드가 플레이어 P[i]에게 배분되는 것이다.

목표 상태를 달성하기 위한 최소 셔플 횟수를 구하라. 어떤 횟수만큼 셔플해도 목표 상태를 만들 수 없다면 -1을 출력하라.

입력

첫째 줄에 카드의 수 N이 주어진다.
둘째 줄에 수열 P의 원소 N개가 공백으로 구분되어 주어진다.
셋째 줄에 수열 S의 원소 N개가 공백으로 구분되어 주어진다.

제한

• 3 ≤ N ≤ 48 (N은 3의 배수)
• P의 각 원소는 0, 1, 2 중 하나이다.
• S는 0부터 N-1까지의 정수가 한 번씩 등장하는 순열이다.

출력

목표 상태를 달성하기 위한 최소 셔플 횟수를 출력한다. 불가능한 경우 -1을 출력한다.

입출력 예시

입력 1

3
2 0 1
1 2 0

출력 1

2

입력 2

6
0 1 2 0 1 2
1 4 0 3 2 5

출력 2

0

입력 3

3
1 0 2
0 2 1

출력 3

-1

입력 4

12
1 1 2 0 2 0 1 0 2 2 1 0
5 0 9 7 1 8 3 10 4 11 6 2

출력 4

59