← 返回题目列表

Codeforces · 404/C

C. 恢复图表

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

Valera 有一个无向连通图,没有自环和由 n 个顶点组成的多条边。该图有一个有趣的属性:其每个顶点最多有 k 条边。为了方便起见,我们假设图顶点由 1 到 n 的整数索引。

有一天,Valera 计算了从图的一个顶点到所有其他顶点的最短距离,并将它们写在数组 d 中。因此,数组的元素 d[i] 显示了从 Valera 选择的顶点到顶点编号 i 的最短距离。

然后发生了一些无法挽回的可怕事情。瓦莱拉丢失了最初的图表。不过,他还有d阵。帮助他恢复丢失的图表。

输入

第一行包含两个空格分隔的整数 n 和 k (1 ≤ k < n ≤ 105)。数字 n 显示原始图中的顶点数。数字 k 表明最多有 k 条边与原始图中的每个顶点相邻。

第二行包含空格分隔的整数 d[1], d[2], ..., d[n] (0 ≤ d[i] < n)。数字 d[i] 表示从 Valera 选择的顶点到顶点编号 i 的最短距离。

输出

如果 Valera 在笔记中犯了错误并且所需的图表不存在,请在第一行中打印数字 -1。否则,在第一行中打印整数 m (0 ≤ m ≤ 106) — 找到的图中的边数。

在接下来的 m 行中,每一行打印两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),表示连接编号为 ai 和 bi 的顶点的边。该图不应包含自环和多重边。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3 2
0 1 1

输出 #1

3
1 2
1 3
3 2

输入 #2

4 2
2 0 1 3

输出 #2

3
1 3
1 4
2 3

输入 #3

3 1
0 0 0

输出 #3

-1