Limits 2s, 512 MB

There are N players (numbered from 1 to N) sitting around a round table. Player 2 is sitting at the right hand side of Player 1, Player 3 is sitting at the right hand side of Player 2... and Player 1 is sitting at the right hand side of Player N. They are playing an interesting game involving coins. There are 2 sets of coins. Each set contains all the coins from 1 to N taka exactly once. So there are 2N coins in total.

At the start of the game, all the coins are distributed among the N players so that each player gets exactly 2 coins. Then the game begins. At each step of the game, each player takes the higher valued coin of the two coins that he currently has and passes it to the player sitting to his right hand side. The game stops when there is at least one player who is holding two coins of the same value.

You have to report after how many steps the game stops or if the game goes on indefinitely.

Input

The first line of input contains an integer T. Here, T is the number of test cases. T test cases follow.

The first line of each test case contains an integer N denoting the number of players in the game.

Then N lines follow. The i-th (1 <= i <= N) of these N lines contains 2 space separated integers denoting the coins the i-th player has at the start of the game. It is guaranteed that each of the coin from the set 1, 2, 3, ..., N appear exactly twice in these N lines.

Constraints:

1 <= T <= 200

2 <= N <= 1000

Output

For each test case, print one line of output which consists of one integer: the number of steps after the game stops or -1 if it goes on indefinitely.

Sample

InputOutput
3
3
1 3
3 2
1 2
2
1 2
2 1
2
1 1
2 2
2
-1
0

Explanation:

In the first test case, after the first step, the coins that the players are holding are:

Player 1: 1 2

Player 2: 2 3

Player 3: 1 3

After the second step:

Player 1: 1 3

Player 2: 2 2

Player 3: 1 3

So after this step, the 2nd Player is holding two same coins. So the game stops here.

In the second test case, the two players will keep giving each other the coin 2 and game will never stop.

In the third test case, both the players have the same coins at the start of the game. So the game ends immediately.

Submit

Login to submit.

Statistics

80% Solution Ratio
ASH1901041MEarliest, May '21
u1804063Fastest, 0.1s
ASH1901041MLightest, 131 kB
BerlekampMassyShortest, 764B
Toph uses cookies. By continuing you agree to our Cookie Policy.