30830번 - 두 체스판

문제

$N \times N$ 크기의 체스판 두 개에 룩이 각각 $N$개씩 올라가 있다. 룩은 같은 체스판의 같은 열이나 같은 행에 있는 다른 룩을 공격할 수 있다.

두 체스판의 룩을 적절히 교환하여 두 체스판 위의 어떠한 룩도 다른 룩을 공격하지 못하게 만들려고 한다.

룩을 교환하는 행위는 정확히 다음과 같다. 체스판의 $r$행 $c$열을 $(r, c)$와 같이 나타낼 때 1ドル$번 체스판의 $(a,b)$에 있는 룩과 2ドル$번 체스판의 $(c,d)$에 있는 룩을 교환하면 1ドル$번 체스판의 $(c,d)$와 2ドル$번 체스판의 $(a,b)$에 각각 룩이 생기고 기존 위치에 있던 두 룩은 사라진다.

체스판의 한 칸에는 룩이 최대 한 개만 올라가 있을 수 있다. 따라서, 룩이 생길 위치에 이미 다른 룩이 존재한다면 그 룩은 교환할 수 없다. 예를 들어, 1번 체스판의 $(a,b)$에 룩이 있다면 2번 체스판의 $(a,b)$에 있는 룩은 1번 체스판의 $(a,b)$를 제외한 모든 1번 체스판 위의 룩과 교환할 수 없게 되는 것이다.

최소 몇 번의 교환으로 두 체스판 위의 어떠한 룩도 다른 룩을 공격하지 못하게 만들 수 있을까?

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1\leq N\leq 100\ 000)$

다음 $N$개의 줄에 1ドル$번 체스판 위의 각 룩이 있는 행의 번호 $x_i$와 열의 번호 $y_i$가 공백으로 구분되어 주어진다. $(1\leq x_i,y_i\leq N)$

다음 $N$개의 줄에 2ドル$번 체스판 위의 각 룩이 있는 행의 번호 $x_i$와 열의 번호 $y_i$가 공백으로 구분되어 주어진다. $(1\leq x_i,y_i\leq N)$

같은 체스판에서는 같은 좌표가 다시 주어지지 않는다.

출력

두 체스판 위의 어떠한 룩도 다른 룩을 공격할 수 없는 상태를 만들기 위한 최소한의 교환 횟수를 출력한다.

만약 룩을 어떻게 교환하더라도 두 체스판 위의 어떠한 룩도 다른 룩을 공격할 수 없는 상태를 만들 수 없다면 대신 -1을 출력한다.

제한

힌트