Restore Graph

题意翻译

对于n个顶点，我们对其进行加边操作！ 首先题目会给你n,k 再给n个数 第 i 个为$d_i$，就是从某一点开始的到i的最短路。 我们对其加边使其满足这最后的答案，如果不能满足，就是输出-1 一个顶点的度 应该不大于 k Translated by @Bartholomew

题目描述

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.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ k $ $ (1<=k<n<=10^{5}) $ . 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 $ .

输出格式

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<=10^{6}) $ — 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

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