시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 8 7 25.926%

문제

1이상 N이하의 자연수로 이루어진 두 배열 A[1..N], B[1..N]이 있다. 당신은 이 배열들을 정리하여 모든 서로 다른 두 자연수 i, j(1 <= i, j <= N)에 대해서 A[i]≠A[j]이고 B[i]≠B[j]이도록 하려 한다. 즉, 각 배열에 같은 수가 중복되어 나타나지 않도록 하려 한다.

우리가 수행할 수 있는 연산은 Swap(i)라는 연산뿐이다. 이 연산은 A[i]값과 B[i]값을 서로 바꾼다. 예를 들어, A[i]=1, B[i]=2일 때 Swap(i)를 수행하면 A[i]=2, B[i]=1이 되는 것이다.

Swap연산을 가능한 한 적게 수행하여 각 배열에 같은 수가 중복되어 나타나지 않도록 하는 프로그램을 작성하시오. 만약 Swap연산을 아무리 사용해도 배열들을 정리할 수 없다면 -1을 출력한다.

입력

첫째 줄에 자연수 N(1 <= N <= 100,000)이 들어온다. 둘째 줄에 A[1], A[2], …, A[N]을 나타내는 N개의 자연수들이 공백으로 구분되어 들어온다. 셋째 줄에 B[1], B[2], …, B[N]을 나타내는 N개의 자연수들이 공백으로 구분되어 들어온다.

출력

첫째 줄에 사용한 Swap연산을 사용한 횟수, 또는 -1을 출력한다.

예제 입력

10
3 2 7 4 6 5 3 9 1 1
6 8 4 10 8 10 7 5 2 9

예제 출력

5

힌트