English · Original
Chinese · Translation
Formal · Original
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
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 _d__i_, 1, _d__i_, 2, ..., _d__i_, _n_ (0 ≤ _d__i_, _j_ ≤ _n_ - 1), where _d__i_, _j_ — the distance to _j_\-th vertex from the _i_\-th vertex that Petya remembers.
## Output
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.
[samples]
## Note
Picture for the first sample:
<center></center>
[{"iden":"statement","content":"Petya 有一棵包含 #cf_span[n] 个顶点的树，顶点编号为从 #cf_span[1] 到 #cf_span[n] 的整数。但他不小心丢失了这棵树。\n\nPetya 记住了 #cf_span[k] 个顶点的信息：每个顶点到树中 #cf_span[n] 个顶点的距离。\n\n你的任务是恢复任意一棵满足 Petya 记忆信息的树，或判断这样的树不存在。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 30 000]，#cf_span[1 ≤ k ≤ min(200, n)]）——树的顶点数和 Petya 记忆了距离信息的顶点数。\n\n接下来的 #cf_span[k] 行包含记忆的信息。第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[di, 1, di, 2, ..., di, n]（#cf_span[0 ≤ di, j ≤ n - 1]），其中 #cf_span[di, j] 表示从 Petya 记忆的第 #cf_span[i] 个顶点到第 #cf_span[j] 个顶点的距离。\n\n如果不存在合适的树，请输出 _-1_。\n\n否则，输出 #cf_span[n - 1] 行：每行包含两个由边连接的顶点。你可以按任意顺序输出边和边中的顶点。树的顶点编号为从 #cf_span[1] 到 #cf_span[n]。\n\n如果有多种解，输出任意一种即可。\n\n第一个样例的图示：\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 30 000]，#cf_span[1 ≤ k ≤ min(200, n)]）——树的顶点数和 Petya 记忆了距离信息的顶点数。接下来的 #cf_span[k] 行包含记忆的信息。第 #cf_span[i] 行包含 #cf_span[n] 个整数 #cf_span[di, 1, di, 2, ..., di, n]（#cf_span[0 ≤ di, j ≤ n - 1]），其中 #cf_span[di, j] 表示从 Petya 记忆的第 #cf_span[i] 个顶点到第 #cf_span[j] 个顶点的距离。"},{"iden":"output","content":"如果不存在合适的树，请输出 _-1_。否则，输出 #cf_span[n - 1] 行：每行包含两个由边连接的顶点。你可以按任意顺序输出边和边中的顶点。树的顶点编号为从 #cf_span[1] 到 #cf_span[n]。如果有多种解，输出任意一种即可。"},{"iden":"examples","content":"输入\n5 2\n0 1 2 3 2\n2 1 0 1 2\n输出\n2 1\n3 2\n4 3\n5 2\n\n输入\n3 1\n1 2 1\n输出\n-1"},{"iden":"note","content":"第一个样例的图示： "}]}
**Definitions**
Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 30000 $, $ 1 \leq k \leq \min(200, n) $.
Let $ D = (d_{i,j}) \in \mathbb{Z}^{k \times n} $ be the distance matrix, where $ d_{i,j} $ is the distance from remembered vertex $ i $ to vertex $ j $ in the unknown tree.
**Constraints**
1. For each $ i \in \{1, \dots, k\} $, $ d_{i,j} \in \{0, 1, \dots, n-1\} $ for all $ j \in \{1, \dots, n\} $.
2. The distances $ d_{i,j} $ must be realizable as shortest-path distances in some tree $ T $ on $ n $ labeled vertices $ \{1, \dots, n\} $.
3. For each remembered vertex $ i $, $ d_{i,i} = 0 $.
**Objective**
Find a tree $ T = (V, E) $ with $ V = \{1, \dots, n\} $ such that for all $ i \in \{1, \dots, k\} $ and $ j \in \{1, \dots, n\} $, the graph distance between $ i $ and $ j $ in $ T $ equals $ d_{i,j} $.
If no such tree exists, output $-1$. Otherwise, output any such tree as $ n-1 $ edges.
API Response (JSON)
{
"problem": {
"name": "E. Restore the Tree",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF871E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Petya had a tree consisting of _n_ vertices numbered with integers from 1 to _n_. Accidentally he lost his tree.\n\nPetya remembers information about _k_ vertices: distances from each of them to each of...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Petya 有一棵包含 #cf_span[n] 个顶点的树，顶点编号为从 #cf_span[1] 到 #cf_span[n] 的整数。但他不小心丢失了这棵树。\\n\\nPetya 记住了 #cf_span[k] 个顶点的信息：每个顶点到树中 #cf_span[n] 个顶点的距离。\\n\\n你的任务是恢复任意一棵满足 Petya 记忆信息的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 30000 $, $ 1 \\leq k \\leq \\min(200, n) $. \nLet $ D = (d_{i,j}) \\in \\mathbb{Z}^{k \\times n} $ be the distance matrix, where $ d_{i,j} ...",
"is_translate": false,
"language": "Formal"
}
]
}