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.

**Input**

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.

**Output**

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**

3
0 2 3
2 0 3
3 3 0

**Sample Output**

5
1 4
2 4
3 5
4 5

Source:

**Andrew Stankevich's Contest #9**
Submit
Status