AT_arc232_b.Two Flips

There are $N$ cards numbered $1$ to $N$. Card $i$ has an integer $A_i$ written on its front side and an integer $B_i$ written on its back side. For every card, the integers written on the front and back sides are different. Initially, all cards are placed face up (front side up).

You can perform the following operation zero or more times.

• Choose two different cards such that the integers written on their currently facing-up sides are equal, and flip both of them simultaneously.

Determine whether it is possible to reach the state where cards $1$ and $2$ are face down (back side up) and all other cards are face up. If it is possible, find the minimum number of operations required.

You are given $T$ test cases; solve each of them.

有 $N$ 张编号为 $1$ 至 $N$ 的卡片。第 $i$ 张卡片正面写有一个整数 $A_i$，背面写有一个整数 $B_i$。每张卡片的正面与背面所写的整数互不相同。初始时，所有卡片均正面朝上（即正面朝上）。

你可以执行以下操作零次或多次：

• 选择两张不同的卡片，使得它们当前朝上的那一面所写的整数相等，并同时将这两张卡片翻转。

判断是否能够达到如下状态：卡片 $1$ 和卡片 $2$ 均背面朝上（即背面朝上），其余所有卡片均正面朝上。若可以达到该状态，求所需的最少操作次数。

你将得到 $T$ 组测试数据，请对每组数据分别求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

Output $T$ lines. The $i$-th line should contain -1 if it is impossible to reach the target state in the $i$-th test case, and otherwise the minimum number of operations required.

输出 $T$ 行。第 $i$ 行应在第 $i$ 个测试用例中无法到达目标状态时输出 -1，否则输出所需的最少操作次数。

Sample 1 Explanation:
In the first test case, choosing the pairs of cards $(1,3),(2,4),(3,4)$ in this order reaches the target state in three operations. It is impossible to reach the target state in two or fewer operations.

In the second test case, choosing the pairs of cards $(1,3),(1,2),(1,4),(3,4)$ in this order reaches the target state in four operations. Card $1$ may be flipped multiple times along the way.

Constraints

• $1 \le T \le 125000$
• $2 \le N \le 250000$
• $1 \le A_i,B_i \le 2N$ $(1 \le i \le N)$
• $A_i \ne B_i$ $(1 \le i \le N)$
• The sum of $N$ over all test cases in a single input is at most $250000$.
• All input values are integers.

样例 1 解释：
在第一个测试用例中，按顺序选择卡片对 $(1,3)$、$(2,4)$、$(3,4)$，可在三次操作内达到目标状态。无法在两次或更少的操作内达到目标状态。

在第二个测试用例中，按顺序选择卡片对 $(1,3)$、$(1,2)$、$(1,4)$、$(3,4)$，可在四次操作内达到目标状态。在此过程中，卡片 $1$ 可能被多次翻转。

约束条件

• $1 \le T \le 125000$
• $2 \le N \le 250000$
• $1 \le A_i,B_i \le 2N$ $(1 \le i \le N)$
• $A_i \ne B_i$ $(1 \le i \le N)$
• 单个输入中所有测试用例的 $N$ 值之和不超过 $250000$。
• 所有输入值均为整数。