Restore the Tree
Contest: Codeforces Round 440 (Div. 1, based on Technocup 2018 Elimination Round 2)
Difficulty rating: 2900
Tags: graphs, greedy, trees

Petya had a tree consisting of n vertices numbered with integers from 1 to n. Accidentally he lost his tree.

Petya remembers information about k vertices: distances from each of them to each of the n tree vertices.

Your task is to restore any tree that satisfies the information that Petya remembers or report that such tree doesn't exist.

Input format:
The first line contains two integers n and k (2 ≤ n ≤ 30 000, 1 ≤ k ≤ min(200, n)) — the number of vertices in the tree and the number of vertices about which Petya remembers distance information.

The following k lines contain remembered information. The i-th line contains n integers di, 1, di, 2, ..., di, n (0 ≤ di, j ≤ n - 1), where di, j — the distance to j-th vertex from the i-th vertex that Petya remembers.

Output format:
If there are no suitable trees, print -1.

In the other case, print n - 1 lines: each line should contain two vertices connected by edge in the required tree. You can print edges and vertices in an edge in any order. The tree vertices are enumerated from 1 to n.

If there are many solutions print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Picture for the first sample:

Example input:
5 2
0 1 2 3 2
2 1 0 1 2

Example output:
2 1
3 2
4 3
5 2

Example input:
3 1
1 2 1

Example output:
-1

Editorial:
In the beginning, it should be noted that it is possible to find out numbers of vertices from which distances are given, the number of the ith specified vertex is idi, such that di, idi = 0. If there is no such a vertex, or more than one, then there is no answer.
Fix the root equal to some vertex from which distances are given in the input data. Assume root = id1. For any vertex idi, we can find vertices lying in the path from root to this vertex, since for such and only for such vertices d1, v + di, v = d1, idi. And accordingly, the vertex v suitable for this condition will be at a distance d1, v from root. So, we have learned to build a part of a tree that consists of vertices that lie on the path from root to some vertex idi. If we couldn't build the path in such a way, then there is no answer. Time complexity of this phase is O(nk).
Now consider the remaining vertices, in order of increasing depth (distance to the root). Let's consider a fixed vertex v, look at the path from it to root, this path can be divided into 2 parts - (root, u), (u, v) where u is the vertex from the already constructed tree, let's find the deepest of such u, this can be done with O(k) operations by using the fact that u is the deepest vertex among all lca(v, idi), which equals the vertex on the path from root to idi at a depth of d1, idi + d1, v - di, v. Then the ancestor v is the vertex that was added in the same way to the subtree u but with a depth of 1 less, or the vertex u (if the depth u is 1 less than the depth of the vertex v). If no such vertices have been added yet, then there is no answer, since we considered the vertices in order of increasing depth. Time complexity of adding each vertex is O(k).
The resulting tree is also the desired tree. Time complexity of the whole algorithm is O(nk).