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
注意
第一个样本的图片: