CF404C.Restore Graph

Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to n.

One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array d. Thus, element d[i] of the array shows the shortest distance from the vertex Valera chose to vertex number i.

Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array d. Help him restore the lost graph.

瓦莱拉曾拥有一个无向连通图，该图不含自环和重边，共有 $n$ 个顶点。该图具有一个有趣的性质：每个顶点的度数至多为 $k$。为方便起见，我们假设图的顶点编号为 $1$ 到 $n$ 的整数。

某天，瓦莱拉计算了从图中某个顶点到其余所有顶点的最短距离，并将结果记录在数组 $d$ 中。因此，数组中的元素 $d[i]$ 表示瓦莱拉所选定的顶点到编号为 $i$ 的顶点的最短距离。

随后，一场无法挽回的灾难发生了：瓦莱拉丢失了原始图。但他仍保留着数组 $d$。请帮助他恢复这个丢失的图。

The first line contains two space-separated integers n and k (1 ≤ k < n ≤ 105). Number n shows the number of vertices in the original graph. Number k shows that at most k edges were adjacent to each vertex in the original graph.

The second line contains space-separated integers d[1], d[2], ..., d[n] (0 ≤ d[i] < n). Number d[i] shows the shortest distance from the vertex Valera chose to the vertex number i.

第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq k < n \leq 10^5$）。整数 $n$ 表示原图中的顶点数量；整数 $k$ 表示原图中每个顶点的度数至多为 $k$。

第二行包含 $n$ 个以空格分隔的整数 $d[1],\,d[2],\,\dots,\,d[n]$（$0 \leq d[i] < n$）。整数 $d[i]$ 表示 Valera 所选顶点到编号为 $i$ 的顶点的最短距离。

If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer m (0 ≤ m ≤ 106) — the number of edges in the found graph.

In each of the next m lines print two space-separated integers a__i and b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i), denoting the edge that connects vertices with numbers a__i and b__i. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.

如果瓦列拉在笔记中犯了错误，所要求的图不存在，则在第一行输出数字 -1。否则，在第一行输出整数 $m$（$0 ≤ m ≤ 10^6$）——即所找到图中的边数。

接下来的 $m$ 行中，每行输出两个用空格分隔的整数 $a_i$ 和 $b_i$（$1 ≤ a_i, b_i ≤ n$；$a_i ≠ b_i$），表示连接编号为 $a_i$ 和 $b_i$ 的顶点的一条边。该图不应包含自环和重边。如果存在多种可能的答案，输出任意一种即可。