워크 스와핑

정점이 $n$개인 사이클 $C$는 $i = 1, \dots, n - 1$에 대해 정점 $i$와 $i + 1$을 간선으로 잇고, 정점 $n$과 $1$도 간선으로 잇는 그래프이다. $C$의 정점에는 1부터 $n$까지 번호가 붙어 있다.

코인은 $n$개이며, 각 코인에는 $\{1, 2, \dots, n\}$ 중 하나의 번호가 적혀 있다. 같은 번호의 코인이 여러 개 있을 수 있다. 처음에 $C$의 각 정점에는 코인이 하나씩 놓여 있다. 두 정점은 서로 코인을 교환할 수 있다.

$C$의 walk $w = (v_1, v_2, \dots, v_k)$에 대해, walk swapping은 $i = 1, 2, \dots, k - 1$의 순서로 $v_i$와 $v_{i+1}$에 놓인 코인을 서로 바꾸는 것이다. walk는 연속한 두 정점이 서로 다르고 $C$에서 인접한 정점들의 수열이다. $C$를 따라 이동할 때 방문하는 정점들로 생각할 수 있다. $k$를 walk의 길이라 한다. 길이가 $k \geq 2$인 walk에서는 $k - 1$번의 교환이 일어나고, 길이가 1인 walk에서는 교환이 일어나지 않는다.

아래 그림은 정점 4개인 사이클에서 walk $(2, 1, 4, 1)$에 대한 walk swapping의 진행 과정을 보여 준다.

예를 들어 그림의 walk $(2, 1, 4, 1)$은 교환을 3번 일으킨다. 같은 최종 배치는 walk $(1, 2)$로 교환 1번만에도 만들 수 있다.

초기 배치와 최종 배치가 주어진다. 초기 배치를 최종 배치로 바꾸는 walk swapping 중에서 전체 교환 횟수가 최소인 것을 구하라.

첫째 줄에 $C$의 정점 수 $n$ ($1 \leq n \leq 3\,000$)이 주어진다.

둘째 줄에는 $n$개의 정수가 주어진다. 각 정수는 1 이상 $n$ 이하이며 중복될 수 있다. $i$번째 정수는 초기 배치에서 정점 $i$에 놓인 코인의 번호이다.

셋째 줄에는 같은 형식으로 $n$개의 정수가 주어진다. $i$번째 정수는 최종 배치에서 정점 $i$에 놓여야 하는 코인의 번호이다.

초기 배치를 최종 배치로 바꾸는 walk swapping의 교환 횟수 최솟값을 한 줄에 출력한다. 그러한 walk swapping이 없으면 -1을 출력한다.