Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2701
Restore the Tree

Time Limit: 10 Seconds      Memory Limit: 32768 KB      Special Judge

An undirected connected graph with no cycles is called a tree. A vertex with degree equal to one in a tree is called a leaf.

Consider a tree. For each pair of leaves one can determine the distance between these leaves --- the number of edges one needs to walk to get from one leaf to another. Given these distances for all pairs of leaves, you need to restore the tree.


There are mutilple cases in the input file.

The first line of each case contains l --- the number of leaves in the tree (2 <= l <= 200 ). Next l lines contain l integer numbers each --- distances between leaves. It is guaranteed that no distance exceeds 200 , all distances are non-negative, distance from a leaf to itself is zero, and the distance from leaf i to leaf j is equal to the distance from leaf j to leaf i .

There is an empty line after each case.


If it is impossible to restore the tree because no such tree exists, output -1 on the first line of the output file.

In the other case first output n --- the number of vertices in the tree. After that output n-1 pairs of numbers --- edges of the tree, each specified with two vertices it connects. If there are several solutions, output any. First l vertices must correspond to tree leaves as they are described in the input file, other vertices may be numbered in arbitrary order.

There should be an empty line after each case.

Sample Input

0 2 3
2 0 3
3 3 0

Sample Output

1 4
2 4
3 5
4 5

Source: Andrew Stankevich's Contest #9
Submit    Status