Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Game of Two Coins

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.

    Discussion

    Statistics


    70% Solution Ratio

    ASH1901041MEarliest, 1w ago

    arnab000Fastest, 0.2s

    ASH1901041MLightest, 131 kB

    BerlekampMassyShortest, 764B

    Submit

    Login to submit