Problem H
Lost Map

Image by Pixabay Member 12019.

Trade between these villages is very important, since not every village has access to the same supply of natural resources. Many villages produce the same resource, however, so it is useful for villages to know their relative distance to other villages so that they can choose trading partners to minimize overall trading costs. Note that the distance between two villages $a$ and $b$ is the sum of the lengths of the individual roads on the shortest path that connects $a$ and $b$.

A project has been underway to compute the distance between every pair of villages. This information has been incorporated in a table, along with a map that shows the layout of villages and roads that run between them. You have been assigned the task of distributing the table and map to all the villages for the betterment of the regional economy.

Unfortunately, not long after you were given this task, a gust of wind blew the map right out of your hand and into the countryside. Despite your best efforts of searching for it, you have been unable to locate it. You know that you could visit all the villages to reconstruct the map and THEN start distributing the map and table, but this will take twice as long as the original task and the villages will be very displeased with you. You wonder, maybe it’s possible to reconstruct the map given only the table?

Input

The first line of input will contain the integer $n$ ($2 \leq n \leq 2\, 500$), the number of villages in this region. The next $n$ lines will contain $n$ integers each. The $j^{\rm th}$ integer of the $i^{\rm th}$ line is the distance from village $i$ to village $j$. All distances are greater than zero unless $i = j$, less than $10^7$, and it is guaranteed that the distance from village $i$ to village $j$ is the same as the distance from village $j$ to village $i$.

Output

For each test case, output $n-1$ lines with two integers $u$ and $v$ on each line, indicating that there is a road connecting villages $u$ and $v$ in this region. Assume the villages are numbered from $1$ to $n$. Any solution that outputs the original set of roads will be accepted.

4
0 1 1 2
1 0 2 3
1 2 0 3
2 3 3 0

1 2
1 3
1 4

7
0 2 9 1 4 3 3
2 0 11 1 6 3 3
9 11 0 10 5 12 12
1 1 10 0 5 2 2
4 6 5 5 0 7 7
3 3 12 2 7 0 4
3 3 12 2 7 4 0

1 4
1 5
2 4
3 5
4 6
4 7