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.

Input

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.

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 ≤ 106) — the number of edges in the found graph.

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

Sample test(s)

input

3 2
0 1 1

output

3
1 2
1 3
3 2

input

4 2
2 0 1 3

output

3
1 3
1 4
2 3

input

3 1
0 0 0

output

-1

########################editorial########################

  in this problem 1 st need to decide whether it is possinble to form a graph or not ..  for that node with dist 0 (starting )can form k no of connections from from node with dist 1 now all node with dist 1 can form maximum k-1 connections with node of  dist k-1 , (sice that noode is already connected with node with dist 0 ) and so on ...

finally if answer exist than for the formation of graph connect node with dist x to node with dist x-1, (but alco check that if node with dist x-1 must connect with maximum k no of node for that do hassing of node connected with all nodes )......

################CODE############

#include<iostream>

using namespace std;

long long int has[10001000];

long long int cnt[10001000];

long long int cp[10001000];

#include<bits/stdc++.h>

int main()

 {

 long long int n,k;

 long long int max_level=0;

  cin>>n>>k;

 vector<pair<long long int,long long int> > v;

 long long int start=0;

  for(long long int i=0;i<n;i++) 

   {

     long long int zz;

      cin>>zz;

      v.push_back(make_pair(zz,i+1));

      if(zz==0) start=i+1;

      has[zz]++;// count of occurance of dist x 

      if(zz>max_level) max_level=zz;

 }

   

 sort(v.begin(),v.end());

   if(has[1]>has[0]*k || has[0]>1 || has[0]==0)

    {

      cout<<"-1"<<endl;

      return 0;

    }

    cp[0]=0;

    cp[1]=1;

    long long int kk=2;

   for(long long int i=2;i<=n;i++)

    {

     if(has[i]>has[i-1]*(k-1))

      {

       // cout<<"here"<<endl;

       cout<<"-1"<<endl;

       return 0;

      }

      if(v[i].first!=v[i-1].first) cp[kk++]=i;// cp contain the occurance                                                                     //start of new dist  

    }

 kk=-1;

 long long int index=0;

  cout<<n-1<<endl;

   for(long long int i=1;i<n;i++)

    {

        long long int no=v[i].second;

        long long int dist=v[i].first;

         if(v[i].first!=v[i-1].first)

  {

    kk++;

    index=cp[kk];

  }

    

         if(cnt[v[index].second]>=k) index++;// if index no node is                                                                                 //connected with  k nodes 

              cout<<v[index].second<<" "<<v[i].second<<endl;

          cnt[v[index].second]++;

          cnt[v[i].second]++;

    }

  return 0;

 }