401686: GYM100513 K Treeland

Treeland is an ancient country located on the territory of the modern Berland many many years ago. It is a well-known fact that Treeland consisted of n cities connected with n - 1 bidirectional roads. It was possible to travel from any city to any other one along the roads. The cities were numbered from 1 to n.

Nowadays we do not know what cities were connected by roads directly, but recently archaeologists have found new information that can help to reconstruct the road network of Treeland.

They found an ancient library with the diaries of a well-known traveler Biklouho-Baclay. The diaries contain interesting information: for each city i there is a list of all cities in the order of non-decreasing distance from i. The distances are calculated assuming that each road has length 1, so a distance between cities is the minimum number of roads to travel between them.

Formally, for each city i there is a list containing a permutation of cities (numbers from 1 to n) in such order that d(i, c_i, j) ≤ d(i, c_{i, j + 1}) for every j = 1... n - 1, where d(x, y) is a distance between cities x and y. Obviously, c_i, 1 = i for each i. The cities that are equidistant from i can be listed in any order.

Your task is to restore a possible road network consistent with the found lists.

The input consists of several test cases. The first line contains integer number t (1 ≤ t ≤ 1000) — the number of test cases.

Then t blocks follow, each describing a single test case. The first line of a block contains integer number n (2 ≤ n ≤ 2000) — the number of cities. The following n lines contain lists C_i, one list per line.

It is guaranteed that the required road network exists for each test case. The sum of n over all test cases doesn't exceed 2000.

For each test case print n - 1 lines describing roads. Each line should contain a pair of cities connected with a road. You may print the roads and cities in a pair in any order. Print a blank line after the output of a test case.

If there are many solutions, print any of them.

3
2
1 2
2 1
5
1 4 5 3 2
2 3 4 1 5
3 4 2 5 1
4 3 1 5 2
5 4 3 1 2
3
1 3 2
2 1 3
3 1 2

2 1 



2 3
3 4
5 4
4 1 


2 1
3 1