← 返回题目列表

Codeforces · 871/E

E. 恢复树

中文机器翻译题面 查看原题

Petya 有一个由 n 个顶点组成的树,顶点编号为 1 到 n 的整数。不小心,他失去了他的树。

Petya 记住有关 k 个顶点的信息:每个顶点到 n 个树顶点中每个顶点的距离。

你的任务是恢复任何满足 Petya 记住的信息的树,或者报告此类树不存在。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 30 000, 1 ≤ k ≤ min(200, n)) — 树中的顶点数以及 Petya 记住距离信息的顶点数。

以下 k 行包含记住的信息。第 i 行包含 n 个整数 di, 1, di, 2, ..., di, n (0 ≤ di, j ≤ n - 1),其中 di, j — Petya 记住的第 i 个顶点到第 j 个顶点的距离。

输出

如果没有合适的树,则打印-1。

在另一种情况下,打印 n - 1 行:每行应包含所需树中通过边连接的两个顶点。您可以按任意顺序打印边和边中的顶点。树的顶点从 1 到 n 进行枚举。

如果有很多解决方案,则打印其中任何一个。

示例

输入 #1

5 2
0 1 2 3 2
2 1 0 1 2

输出 #1

2 1
3 2
4 3
5 2

输入 #2

3 1
1 2 1

输出 #2

-1

注意

第一个样本的图片: