순열 정렬

면접 대비

시간 제한2초메모리 제한512 MB

요약

매일 칠판의 각 값 x를 Q[x]로 바꿀 때, 수열 P가 오름차순이 되는 최소 일수 d를 구하고 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

어느 날(0일째라고 하자) 칠판에 $N$ 개의 정수로 이루어진 순열 $P$ 가 한 줄로 적혀 있는 것을 발견한다. 마침 $N$ 개의 정수로 이루어진 또 다른 순열 $Q$ 도 가지고 있어서, 이 순열들로 놀기로 한다.

1, 2, 3일째의 매일 아침마다 칠판의 모든 수를 다음과 같이 다시 쓴다. 수 $x$ 를 지우고 같은 위치에 수 $Q_x$ 를 쓴다. $d$ 일째 저녁에 칠판의 수열이 증가하는 순서로 정렬되어 있게 하는 최소 음이 아닌 정수 $d$ 를 구하시오.

입력

입력은 아래 형식의 단일 테스트 케이스로 이루어진다.

입력의 첫째 줄에는 정수 $N$ ( $1 \le N \le 200$ )이 주어진다. 둘째 줄에는 순열 $P$ 를 나타내는 $N$ 개의 정수 $P_1$ , $\ldots$ , $P_N$ ( $1 \le P_i \le N$ )이 주어진다. 셋째 줄에는 순열 $Q$ 를 나타내는 $N$ 개의 정수 $Q_1$ , $\ldots$ , $Q_N$ ( $1 \le Q_i \le N$ )이 주어진다.

출력

$d$ 일째 저녁에 칠판의 수열이 증가하는 순서로 정렬되어 있게 하는 최소 음이 아닌 정수 $d$ 를 출력한다. 그러한 $d$ 가 존재하지 않으면 대신 $-1$ 을 출력한다. 답이 $10^{18}$ 을 넘지 않음이 보장된다.

예제3

예제 1
입력
```
6
2 3 1 4 5 6
3 1 2 5 4 6
```
예상 출력
```
4
```
예제 2
입력
```
6
1 2 3 4 5 6
3 1 2 5 4 6
```
예상 출력
```
0
```
예제 3
입력
```
6
2 3 1 4 5 6
3 4 5 6 1 2
```
예상 출력
```
-1
```