CF871E.Restore the Tree

Petya 有一棵包含 $n$ 个顶点的树，这些顶点编号为 $1$ 到 $n$ 的整数。不小心，他把树弄丢了。

Petya 还记得关于 $k$ 个顶点的信息：从每一个这样的顶点到树上每一个顶点的距离。

你的任务是还原出任意一棵符合 Petya 记忆中信息的树，或者报告无解。

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 30000$，$1 \leq k \leq \min(200,n)$），分别表示树的顶点数以及 Petya 记得距离信息的顶点数。

接下来的 $k$ 行中，每行包含 $n$ 个整数 $d_{i,1}, d_{i,2}, \dots, d_{i,n}$（$0 \leq d_{i,j} \leq n-1$），其中 $d_{i,j}$ 表示从 Petya 记得的第 $i$ 个顶点到第 $j$ 个顶点的距离。

如果不存在满足条件的树，输出 $-1$。

否则，输出 $n-1$ 行，每行包含两个被树的边连接的顶点编号。你可以按照任意顺序输出边及边中两个顶点的顺序，树的顶点编号为 $1$ 到 $n$。

如果有多种方案，输出其中任意一种都可以。

第一个样例的示意图：

由 ChatGPT 5 翻译