Tidying Arrays
Time limit2sMemory limit128 MB
Given two arrays of 1..N, find the minimum number of index swaps between A and B so neither array has duplicate values, or report impossibility.
- Level
Medium6 of 10
- Topics
- Graph, Union-find, Greedy
- Solved
- No attempts yet
Problem
There are two arrays A[1..N] and B[1..N], each consisting of natural numbers from 1 to N. For an index i, one Swap(i) operation exchanges the values of A[i] and B[i].
The goal is to tidy the arrays so that no number appears more than once in A, and no number appears more than once in B.
Find the minimum possible number of Swap operations needed to achieve this. If it is impossible to make both arrays contain no duplicates, print -1.
Input
The first line contains a natural number N (1 <= N <= 100000).
The second line contains A[1], A[2], ..., A[N], separated by spaces.
The third line contains B[1], B[2], ..., B[N], separated by spaces.
Every array element is a natural number between 1 and N, inclusive.
Output
Print the minimum number of required Swap operations on the first line. If it is impossible, print -1.