AT_arc232_b [ARC232B] Two Flips

$ 1 $ から $ N $ までの番号のついた $ N $ 枚のカードがあり，カード $ i $ の表には整数 $ A_i $ ，裏には整数 $ B_i $ が書かれています． どのカードについても，表と裏に書かれた整数は異なります． はじめ，すべてのカードは表を上にして置かれています． あなたは，次の操作を $ 0 $ 回以上行うことができます． - 現在上になっている面に書かれた整数が等しい，異なる $ 2 $ 枚のカードを選び，その $ 2 $ 枚を同時に裏返す． カード $ 1,2 $ は裏が上になっており，それ以外のすべてのカードは表が上になっている状態にすることが可能か判定してください． 可能な場合は，必要な操作回数の最小値を求めてください． $ T $ 個のテストケースが与えられるので，それぞれについて答えてください．

入力は以下の形式で標準入力から与えられる． > $ 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` を，可能な場合は必要な操作回数の最小値を出力せよ．

### Sample Explanation 1 $ 1 $ 番目のテストケースでは，選ぶカードの組を順に $ (1,3),(2,4),(3,4) $ とすると， $ 3 $ 回の操作で目標の状態になります． $ 2 $ 回以下の操作で目標の状態にすることはできません． $ 2 $ 番目のテストケースでは，選ぶカードの組を順に $ (1,3),(1,2),(1,4),(3,4) $ とすると， $ 4 $ 回の操作で目標の状態になります． 途中でカード $ 1 $ を複数回裏返してもかまいません． ### 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) $ - $ 1 $ つの入力に含まれるテストケースの $ N $ の総和は $ 250000 $ 以下である． - 入力はすべて整数である．