B - Two Flips 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

1 から N までの番号のついた N 枚のカードがあり，カード i の表には整数 A_i，裏には整数 B_i が書かれています． どのカードについても，表と裏に書かれた整数は異なります． はじめ，すべてのカードは表を上にして置かれています．

あなたは，次の操作を 0 回以上行うことができます．

  • 現在上になっている面に書かれた整数が等しい，異なる 2 枚のカードを選び，その 2 枚を同時に裏返す．

カード 1,2 は裏が上になっており，それ以外のすべてのカードは表が上になっている状態にすることが可能か判定してください． 可能な場合は，必要な操作回数の最小値を求めてください．

T 個のテストケースが与えられるので，それぞれについて答えてください．

制約

  • 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)
  • 1 つの入力に含まれるテストケースの N の総和は 250000 以下である．
  • 入力はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

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

出力

T 行出力せよ． i 行目には，i 番目のテストケースにおいて目標の状態にすることが不可能な場合は -1 を，可能な場合は必要な操作回数の最小値を出力せよ．

入力例 1

8
4
1 4
2 5
1 3
2 3
4
1 2
2 1
1 3
1 3
2
1 2
1 2
2
1 2
2 1
3
1 2
3 4
1 3
5
1 4
4 5
1 2
2 3
3 1
8
1 9
7 10
1 2
3 2
3 4
5 4
5 6
7 6
3
1 2
3 4
2 3

出力例 1

3
4
1
-1
2
5
7
-1

1 番目のテストケースでは，選ぶカードの組を順に (1,3),(2,4),(3,4) とすると，3 回の操作で目標の状態になります． 2 回以下の操作で目標の状態にすることはできません．

2 番目のテストケースでは，選ぶカードの組を順に (1,3),(1,2),(1,4),(3,4) とすると，4 回の操作で目標の状態になります． 途中でカード 1 を複数回裏返してもかまいません．

Score : 800 points

Problem Statement

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.

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.

Input

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

Output

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.

Sample Input 1

8
4
1 4
2 5
1 3
2 3
4
1 2
2 1
1 3
1 3
2
1 2
1 2
2
1 2
2 1
3
1 2
3 4
1 3
5
1 4
4 5
1 2
2 3
3 1
8
1 9
7 10
1 2
3 2
3 4
5 4
5 6
7 6
3
1 2
3 4
2 3

Sample Output 1

3
4
1
-1
2
5
7
-1

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.