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^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.


-----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^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.


-----Examples-----
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

Difficulty: interview

Starter code:

Solutions:
from math import ceil

def mkgr(n, srs, k):
  res = [str(n-1)]
  for d in srs[1]:
    res.append("%i %i" % (srs[0][0]+1, d+1))
  for i in range(2, len(srs)):
    h, hs= 0, 0
    for j in range(len(srs[i])):
      res.append("%i %i" % (srs[i][j]+1, srs[i-1][h]+1))
      hs += 1
      if hs == k-1:
        h += 1
        hs = 0
      
  return res

def test(n,k,dists):
  m = max(dists)
  srs = [[] for i in range(m+1)]
  for i in range(n):
    srs[dists[i]].append(i)
  if [] in srs:
    return ["-1"]
  if len(srs[0]) != 1:
    return ["-1"]
  if len(srs[1]) > k:
    return ["-1"]
  for i in range(1, m):
    if ceil(len(srs[i+1])/len(srs[i])) + 1 > k:
      return ["-1"]
  return mkgr(n, srs, k)

n, k = list(map(int, input().split()))
dists = list(map(int, input().split()))
res = test(n,k,dists)
print("\n".join(res))


n, k = list(map(int, input().split()))
d = list(map(int, input().split()))

dmax = max(d)

nv = [[] for i in range(dmax+1)]
v = [0] * (dmax+1)

for i, dist in enumerate(d):
    nv[dist].append(i)
    v[dist] += 1

flag = True
if v[0] != 1 or v[1] > k:
    flag = False
else:
    for i in range(2, dmax+1):
        if v[i] > (k-1) * v[i-1] or v[i] == 0:
            flag = False
            break

if flag:
    print(n-1)
    for vrtx in nv[1]:
        print(nv[0][0] + 1, vrtx + 1)
    for i, vs in enumerate(nv[1:-1]):
        for j, vrtx in enumerate(vs):
            m = 0
            while m < (k-1):
                if (j*(k-1) + m) < len(nv[i+2]):
                    print(vrtx + 1, nv[i+2][j*(k-1) + m] + 1)
                    m += 1
                else:
                    break

else:
    print(-1)


n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)


n, k = map(int, input().split())
t = list(map(int, input().split()))
s, p = [], [[] for i in range(max(t) + 1)]
for i, j in enumerate(t, 1): p[j].append(str(i))
if len(p[0]) - 1: print('-1')
else:
    for i in range(1, len(p)):
        if k * len(p[i - 1]) < len(p[i]):
            print('-1')
            return
        j, u, v = 0, len(p[i]) // k, len(p[i]) % k
        for x in range(u):
            s += [p[i - 1][x] + ' ' + p[i][y] for y in range(j, j + k)]
            j += k
        s += [p[i - 1][u] + ' ' + p[i][y] for y in range(j, j + v)]
        if i == 1: k -= 1
    print(len(s))
    print('\n'.join(s))

from collections import deque

def solve():
	n, k = list(map(int, input().split()))
	a = list(enumerate(map(int, input().split()), 1))
	a.sort(key=lambda x: x[1])
	
	if a[0][1]:
		print(-1)
		return
	e = []
	q = deque([[1, k, a[0][0]]])
	
	for i, x in a[1:]:
		while q and q[0][0] < x:
			q.popleft()
		if not q or q[0][0] != x:
			print(-1)
			return
		if k > 1:
			q.append([x+1, k-1, i])
		e.append((q[0][2], i))
		q[0][1] -= 1
		if not q[0][1]:
			q.popleft()
	print(len(e))
	print('\n'.join(' '.join(map(str, x)) for x in e))

def __starting_point():
	solve()

__starting_point()

n, k = map(int, input().split())
d = sorted(zip(list(map(int,input().split())), range(0,n)))
last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last < j and (du[last] == k or d[last][0] + 1 != d[j][0]):
        last += 1
    if last == j or d[0][0] != 0:
        print(-1)
        break
    fa[j] = last
    du[j] += 1
    du[last] += 1
else:
    print(n - 1)
    for j in range(1, n):
        print(d[fa[j]][1]+1,d[j][1]+1)

import os
import sys
import copy

# sys.stdin = open(os.path.join(os.path.dirname(__file__), '7.in'))

n,k = map(lambda x:int(x), input().split())
# G = [[-1 for _ in range(n+1)] for _ in range(n+1)]
C = [0 for _ in range(n+1)]
d = [ {'d':int(_),'idx':i+1} for i, _ in enumerate(input().split())]
d.sort(key = lambda x: x['d'])

# print(d)
pos = True
eg = 0
reeg = []
# multi zero number
cz = 0
for dis in d:
    if dis['d'] == 0:
        cz += 1 

if cz != 1:
    pos= False
else:
    first = True
    c_vertex = -1
    Preidx = 0
    PPreidx = 0
    pd = 2<<30
    for i,vx in enumerate(d):
        if i == 0 :
            c_vertex = vx['idx']
            pd = 0
            continue   
        # print(vx)
        find = False
        if vx['d'] == pd:
            vvbg= PPreidx
        else:
            vvbg = Preidx
        # print("ss",vx,d[vvbg],PPreidx,Preidx)
        
        while vvbg < i:
            # print("ss",vx,d[vvbg])
            if C[d[vvbg]['idx']] < k:
                if d[vvbg]['d'] + 1 != vx['d']:
                    pos = False
                    break
                # G[d[vvbg]['idx']][vx['idx']] = 1
                C[d[vvbg]['idx']] += 1
                C[vx['idx']] += 1
                eg += 1
                find = True
                reeg.append((d[vvbg]['idx'],vx['idx']))
                break
            # else:
            #     Preidx += 1
            vvbg += 1
                # print(reeg)
        if not find:
            pos = False

        if i >= 1 and vx['d'] != pd:
            # print("ppre", Preidx, PPreidx)
            PPreidx = Preidx
            Preidx=i
        pd = vx['d']
        
if pos:
    print(eg)
    for a,b in reeg:
        print(a,b)
else:
    print(-1)



n, k = list(map(int, input().split()))
nodes = [[] for _ in range(n+1)]
edges = []

for node, dist in enumerate(map(int, input().split())):
    nodes[dist].append(node)

if len(nodes[0]) != 1 or len(nodes[1]) > k:
    print(-1)
else:
    for i in range(1, n):
        if len(nodes[i])*(k-1) < len(nodes[i+1]):
            print(-1)
            return
    for i in range(n):

        next = 0

        if len(nodes[i+1]) > 0:
            for j, node in enumerate(nodes[i]):

                current = 0

                while current < (k if i == 0 else k-1) and next < len(nodes[i+1]):
                    edges.append((node+1, nodes[i+1][next]+1))
                    next += 1
                    current += 1

    print(len(edges))
    print('\n'.join([' '.join([str(x[0]), str(x[1])]) for x in edges]))


n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=list(map(int,input().split()))
d=list(zip( list(map(int,input().split())),list(range(0,n)) ))
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)



n,k=map(int,input().split())
d=zip( list(map(int,input().split())),range(0,n) )
d=sorted(d)

last=0
du=[0]*n
fa=[0]*n
flag=1
for j in range(1,n):
    while last<j and ( du[last]==k or d[last][0]+1!=d[j][0] ):
        last+=1
    if last==j or d[0][0]!=0:
        print(-1)
        break
    fa[j]=last
    du[j]+=1
    du[last]+=1
else:
    print(n-1)
    for j in range(1,n):
        print(d[fa[j]][1]+1,d[j][1]+1)

n, k = map(int, input().split())
t = list(map(int, input().split()))
s, p = [], [[] for i in range(max(t) + 1)]
for i, j in enumerate(t, 1): p[j].append(str(i))
if len(p[0]) - 1: print('-1')
else:
    for i in range(1, len(p)):
        if k * len(p[i - 1]) < len(p[i]):
            print('-1')
            return
        j, u, v = 0, len(p[i]) // k, len(p[i]) % k
        for x in range(u):
            s += [p[i - 1][x] + ' ' + p[i][y] for y in range(j, j + k)]
            j += k
        s += [p[i - 1][u] + ' ' + p[i][y] for y in range(j, j + v)]
        if i == 1: k -= 1
    print(len(s))
    print('\n'.join(s))

class RestoreGraph():
    def __init__(self,n, k, dis_values):
        self.dis_values = dis_values
        self.n = n
        self.k = k

    def generate_graph(self):
        dis_pairs = [(self.dis_values[i],i) for i in range(len(self.dis_values))]
        dis_pairs = sorted(dis_pairs)
        if dis_pairs[0][0] != 0:
            print(-1)
            return
        count = [0]*self.n
        parent = [-1]*self.n
        ind = 0
        for i in range(1, self.n):
            if dis_pairs[ind][0] != dis_pairs[i][0]-1 or count[ind] == self.k:
                ind = ind+1
                while(ind < i and (dis_pairs[ind][0] < dis_pairs[i][0]-1 or count[ind] == self.k)):
                    ind += 1
                if dis_pairs[ind][0] != dis_pairs[i][0]-1 or count[ind] == self.k:
                    print(-1)
                    return
            parent[i] = ind
            count[i] += 1
            count[ind] += 1
        print(self.n-1)
        for i in range(1,n):
            print(dis_pairs[i][1]+1, dis_pairs[parent[i]][1]+1)


n, k = list(map(int,input().strip(' ').split(' ')))
arr = list(map(int,input().strip(' ').split(' ')))

graph = RestoreGraph(n,k,arr)
graph.generate_graph()


'''input
3 1
0 1 2
'''
from sys import stdin
import collections
import math
import queue


# main starts
n, k = list(map(int, stdin.readline().split()))
distance = list(map(int, stdin.readline().split()))

# n = 65535; k = 3
# distance = []
# for i in range(16):
# 	for j in range(2 **i):
# 		distance.append(i)

for i in range(n):
	distance[i] = [i + 1, distance[i]]

distance = sorted(distance, key = lambda x:x[1])

if distance[0][1] != 0:
	print(-1)
	return

edges = []
i = 1
buff = collections.deque()
buff.append(distance[0])

while len(buff) > 0 and i < n:
	prev_node, prev_dist = buff.popleft()

	count = 0
	while i < n:
		if prev_dist + 1 == distance[i][1]:
			if (count == k and prev_dist == 0) or (count == k - 1 and prev_dist != 0):
				break
			edges.append([prev_node, distance[i][0]])
			buff.append(distance[i])
			count += 1
			i += 1


		elif prev_dist + 2 == distance[i][1]:
			break
		else:	
			print(-1)
			return
if i != n:
	print(-1)
	return
print(len(edges))
for i in edges:
	print(*i)

n, k = list(map(int, input().split()))
d = list(map(int, input().split()))
max_d = max(d)
levels = [[] for i in range(max_d+1)]
graph = {}
for i in range(len(d)):
    levels[d[i]].append(i+1)

def do_this():
    nonlocal n,k, d, max_d, levels, graph
    q = []
    last_level = levels[0]
    if len(last_level) != 1:
        print(-1)
        return
    for i in range(1, max_d+1):
        if i == 2:
            k = k-1
        if k == 0:
            print(-1)
            return
        cur_level = levels[i]
        for j in range(len(cur_level)):
            if j/k >= len(last_level):
                print(-1)
                return
            q.append((last_level[int(j/k)], cur_level[j]))
        last_level = cur_level
    print(len(q))
    for a,b in q: print(a, b)

do_this()


n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

d = {}
for idx, x in enumerate(a):
    if x not in d:
        d[x] = [idx]
    else:
        d[x].append(idx)

if 0 not in d or len(d[0]) != 1:
    print(-1)
    import sys; return

res = []

for x in range(1, max(d.keys())+1):
    if x not in d or len(d[x]) > len(d[x-1])*(k if x-1 is 0 else k-1):
        print(-1)
        import sys; return
    t = d[x][:]
    p = d[x-1][:]
    z = (0 if x-1 is 0 else 1)
    while(t):
        res.append((p[-1]+1, t[-1]+1))
        del t[-1]
        z += 1
        if z == k:
            z = 1
            del p[-1]
        
print(len(res))
for x, y in res:
    print(x, y)

n, k = input().split()
n = int(n)
k = int(k)

d = input().split()
d = [int(x) for x in d]

freq = [[] for _ in range(n)]

for idx, x in enumerate(d):
  freq[x].append(idx+1)

if len(freq[0]) != 1:
  print('-1')
  import sys; return
  
solution = []
for i in range(1, n):
  if i-1 != 0:
    new_k = k-1
  else:
    new_k = k
  if len(freq[i]) > len(freq[i-1]) * new_k:
    print('-1')
    import sys; return
  prev = freq[i-1]
  idx = 0
  counter = 0
  for x in freq[i]:
    solution.append((prev[idx], x))
    counter += 1
    if counter == (k if i-1 == 0 else k-1):
      idx += 1
      counter = 0

print(len(solution))
for x, y in solution:
  print(x, y)



import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,k = I()
d=I();ed=[]
d=sorted([[d[i],i+1] for i in range(n)])
i=1;cur=[d[0][1]];l=0;f=1
if d[0][0]!=0:
	f=0
while i<n:
	x=len(cur);m=x*(k-1) if i!=1 else k
	r=0;j=0;ll=[]
	while i<n and d[i][0]==l+1:
		if j>=x:
			r=m+1;break
		ed.append([cur[j],d[i][1]])
		ll.append(d[i][1])
		i+=1;r+=1
		if r==((j+1)*(k-1) if l!=0 else k):
			j+=1
	if r==0 or r>m:
		f=0;break
	cur=list(ll)
	l+=1
if f:
	print(len(ed))
	for i in range(len(ed)):
		print(*ed[i])
else:
	print(-1)



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    n, k = read_ints()
    d = read_ints()
    S = [[] for _ in range(n)]
    for i in range(n):
        S[d[i]].append(i)
    if len(S[0]) != 1:
        return -1
    G = [[] for _ in range(n)]
    degree = [0]*n
    depth = 1
    construct_count = 1
    edges = []
    for depth in range(1, n):
        i = 0
        prev_len = len(S[depth-1])
        if len(S[depth]) == 0:
            break
        for vertex in S[depth]:
            parent_vertex = S[depth-1][i%prev_len]
            degree[parent_vertex] += 1
            if degree[parent_vertex] > k:
                return -1
            degree[vertex] += 1
            if degree[vertex] > k:
                return -1
            G[parent_vertex].append(vertex)
            edges.append((parent_vertex, vertex))
            construct_count += 1
            i += 1
    if construct_count != n:
        return -1
    print(len(edges))
    for u, v in edges:
        print(u+1, v+1)

    
def __starting_point():
    if solve() == -1:
        print(-1)

__starting_point()

def solve(n,k,d):
	dist = [[] for i in range(n)]
	for u in range(n):
		dist[d[u]].append(u)
	if len(dist[0])!=1:
		return []

	ans = []
	for t in range(1,n):
		nxt = []
		j = 0
		lim = k if t==1 else (k-1)
		ctr = 0
		for u in dist[t]:
			if ctr==lim:
				ctr = 0
				j += 1
			if j==len(dist[t-1]):
				return []
			else:
				ans.append((dist[t-1][j]+1,u+1))
				ctr += 1
	return ans

n, k = list(map(int,input().split()))
d = [int(x) for x in input().split()]
ans = solve(n,k,d)
if ans==[]:
	print(-1)
else:
	print(len(ans))
	for e in ans:
		print(*e)