AT_arc232_b [ARC232B] 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.

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 $ 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 Explanation 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. ### 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.