2245번 - 배열 정리하기

문제

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을 출력한다.

제한

힌트