CodeForces 404C Ivan and Powers of Two

Ivan and Powers of Two

Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

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.

Input

The first line contains two space-separated integers n and k(1 ≤ k < n ≤ 10⁵). 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.

Output

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⁶) — 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.

Sample Input

Input

3 2
0 1 1

Output

Input

4 2
2 0 1 3

Output

Input

3 1
0 0 0

Output

-1

由图上的一点到其他点的距离，还原整个图。易知原图必定是一个树，因为给出的是一个点到其他点的距离，说明这个点到其他的点必定是唯一联通的（即使原图是多路联通，对每个同路取最小值后，也只剩
下一条通路了）。所以就是求一个树的过程。
我们把各个点按照到根节点的距离分类。这些距离可以是1 2 3.。。。n-1；
然后按照距离从小到大连接，每次的距离增加1，所以新增加的点是和上一个的点直接相连的。由于距离根节点距离为1的点开始没有连线，所以起始边数为0，之后的必定和比它到根节点距离少1的
节点连线，所以边数起始值是1.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#define max1 100005
using namespace std;
int main()
{
    int n,k;
   vector< pair<int,int> >ans;
    vector<int >dis[max1];
    scanf("%d%d",&n,&k);
    int m=0;
    for(int i=1;i<=n;i++)
    {
        int di;
        scanf("%d",&di);
        m=max(di,m);
        dis[di].push_back(i);
    }
    if(dis[0].size()!=1) {printf("-1
");return 0;}
    for(int i=1;i<=m;i++)
    {
        int edge=(i!=1),node=0;
        for(int j=0;j<dis[i].size();j++)
        {
            if(edge==k)
            {
                node++;
                edge=(i!=1);
            }
            if(node==dis[i-1].size())
            {
                printf("-1
");
                return 0;
            }
            ans.push_back(make_pair(dis[i-1][node],dis[i][j]));
            edge++;

        }
    }
    printf("%d
",n-1);
    for(int i=0;i<n-1;i++)
        printf("%d %d
",ans[i].first,ans[i].second);
    return 0;
}

View Code