A. Salahiano-utiful Arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Salahiano came up with this problem with a totally different story that none of the judges was able to understand. He changed the story multiple times until finally, it became humanly understandable.

We define an array of integers to be a Salahiano-utiful Array if it's elements are distinct.

Salahiano will give you two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$. In one operation, you can choose some index $$$i$$$ $$$(1 \le i \le N)$$$ and:

  • Exchange the values of $$$A_i$$$ and $$$B_i$$$, i.e swap$$$(A_i, B_i)$$$.

What is the minimum number of operations needed to make both $$$A$$$ and $$$B$$$ Salahiano-utiful Arrays? Or report that it's impossible.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ — the length of the arrays $$$A$$$ and $$$B$$$.

Then, $$$N$$$ lines follow, the $$$i_{th}$$$ of them contains the values $$$A_i$$$ and $$$B_i$$$ $$$(1 \le A_i,B_i \le 2 \cdot N)$$$

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase output a single integer — the minimum possible number of operations needed or $$$-1$$$ if it is impossible.

Example
Input
3
3
1 3
3 2
1 2
2
1 2
1 1
5
1 9
10 3
10 3
2 5
7 5
Output
1
-1
2