E. Any Tree ?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer grid $$$a$$$ containing $$$n$$$ rows and $$$n$$$ columns. Let $$$a_{i,j}$$$ denote the value at the $$$i$$$-th row from the top and $$$j$$$-th column from the left.

Now your task is to construct a tree (undirected acyclic graph) containing $$$n$$$ nodes, such that :

  • For every $$$i,j(1 \le i,j \le n)$$$, the smallest value of the node on the path between $$$i$$$ and $$$j$$$ (both inclusive) is $$$a_{i,j}$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains single integer $$$n$$$ ($$$2 \le n \le 10^3$$$).

The next $$$n$$$ lines of each test case contains $$$n$$$ integers $$$a_{i,1},a_{i,2},\cdots,a_{i,n}$$$ ($$$1 \le a_{i,j} \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output

For each test case, print $$$-1$$$ if there is no possible tree.

Otherwise, print $$$n-1$$$ lines — the edges of the tree.

If there are multiple answers output any.

Example
Input
5
4
1 1 1 1
1 2 1 1
1 1 3 3
1 1 3 4
5
1 1 1 1 1
1 2 1 1 1
1 1 3 3 3
1 1 3 4 3
1 1 3 3 5
5
1 1 1 1 2
3 4 1 1 3
3 4 1 1 5
2 3 1 2 3
1 2 3 4 5
6
1 1 1 1 1 1
1 2 2 1 1 2
1 2 3 2 3 1
1 1 2 4 3 2
1 1 3 3 5 2
1 2 1 2 2 6
7
1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 3 1 3 3 3
1 2 1 4 1 1 1
1 1 3 1 5 5 3
1 1 3 1 5 6 3
1 1 3 1 3 3 7
Output
3 4
2 1
1 3
3 5
1 2
4 3
3 1
-1
-1
2 4
3 1
3 6
4 1
7 3
5 6