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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Graph algorithms

Graph traversal


Solutions:
import sys
import itertools as it
import math as mt
import collections as cc
import bisect as bi
I = lambda : list(map(int, input().split()))
(n, k) = I()
l = I()
ar = []
f = cc.defaultdict(list)
ch = cc.defaultdict(int)
for i in range(n):
	ar.append([l[i], i])
	f[l[i]].append(i)
ar.sort(key=lambda x: x[0])
if l.count(0) > 1:
	print(-1)
elif 0 not in l:
	print(-1)
else:
	d = max(l)
	ed = []
	now = 0
	prev = [l.index(0)]
	tf = 1
	while now + 1 <= d:
		cur = set()
		if len(f[now + 1]) == 0:
			tf = 0
			break
		ii = 0
		ll = len(prev)
		if ll * k < len(f[now + 1]):
			tf = 0
			break
		else:
			for j in f[now + 1]:
				if ch[prev[ii]] < k:
					ch[prev[ii]] += 1
					ch[j] += 1
					cur.add(j)
					ed.append([prev[ii] + 1, j + 1])
					ii += 1
					ii %= ll
				else:
					tf = 0
					break
		prev = list(cur)
		now += 1
	if not tf:
		print(-1)
	else:
		print(len(ed))
		for i in ed:
			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) = 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) = 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
	sys.exit(0)
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
		sys.exit(0)
	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 os, sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	cou = [[] for _ in range(n)]
	for i in range(n):
		cou[d[i]].append(i + 1)
	if len(cou[0]) != 1:
		print(-1)
		return
	ans = []
	for i in range(max(d)):
		if len(cou[i]) * (k - 1) + (i == 0) < len(cou[i + 1]):
			print(-1)
			return
		(x, y) = (0, 0)
		for j in cou[i + 1]:
			if x == k - 1 + (i == 0):
				(x, y) = (0, y + 1)
			x += 1
			ans.append((cou[i][y], j))
	print(len(ans))
	for i in ans:
		print(*i)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
import collections
import math
import queue
(n, k) = list(map(int, stdin.readline().split()))
distance = list(map(int, stdin.readline().split()))
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)


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)
if solve() == -1:
	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]))


from collections import deque

def dfs(start, g, wyn, pozostale, d, boole):
	kolejka = [start]
	while kolejka:
		v = kolejka.pop()
		try:
			while pozostale[v] and g[d[v] + 1]:
				pozostale[v] -= 1
				u = g[d[v] + 1].pop()
				if not boole[u]:
					kolejka.append(u)
				(boole[u], boole[v]) = (True, True)
				wyn.append(f'{v + 1} {u + 1}')
				pozostale[u] -= 1
		except:
			pass
	if all(boole):
		print(len(wyn))
		for w in wyn:
			print(w)
	else:
		print(-1)

def main():
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	d = list(map(int, input().split()))
	g = {}
	for i in range(n):
		if d[i] in g:
			g[d[i]].append(i)
		else:
			g[d[i]] = deque()
			g[d[i]].append(i)
	pozostale = n * [k]
	g = dict(sorted(g.items()))
	boole = n * [False]
	try:
		dfs(g[0][0], g, [], pozostale, d, boole)
	except:
		print(-1)
main()


(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
	sys.exit(0)
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
		sys.exit(0)
	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)


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()


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)


(n, k) = map(int, input().split())
a = zip(list(map(int, input().split())), range(0, n))
a = sorted(a)
i = 0
start = [0] * n
count = [0] * n
for j in range(1, n):
	while i < j and (count[i] == k or a[i][0] + 1 != a[j][0]):
		i += 1
	if i == j or a[0][0] != 0:
		print(-1)
		exit(0)
	start[j] = i
	count[j] += 1
	count[i] += 1
print(n - 1)
for k in range(1, n):
	print(a[start[k]][1] + 1, a[k][1] + 1)


(n, k) = map(int, input().split())
d = zip(list(map(int, input().split())), range(1, n + 1))
d = sorted(d)
if d[0][0] != 0:
	print(-1)
else:
	u = 0
	m = 0
	check = True
	graph = []
	deg = [0] * (n + 1)
	for v in range(1, n):
		if deg[d[u][1]] >= k:
			u += 1
		while u < v and d[v][0] != d[u][0] + 1:
			u += 1
		if u == v or deg[d[u][1]] >= k or deg[d[v][1]] >= k:
			print(-1)
			check = False
			break
		graph.append([d[u][1], d[v][1]])
		deg[d[u][1]] += 1
		deg[d[v][1]] += 1
		m += 1
	if check:
		print(m)
		for i in range(0, m):
			print(graph[i][0], graph[i][1])


import sys
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
g = [k] * n
maxi = max(a)
ans = []
if a.count(0) != 1:
	print(-1)
	sys.exit()
i = 1
f = a.index(0)
pref_t = [f]
x = [[] for y in range(maxi + 1)]
for v in range(n):
	x[a[v]].append(v)
while i <= maxi:
	t = x[i]
	w = len(t)
	z = 0
	for o in pref_t:
		z += g[o]
	if z < w:
		print(-1)
		sys.exit()
	u = 0
	for l in pref_t:
		while w > 0 and g[l] > 0:
			g[l] -= 1
			g[t[u]] -= 1
			w -= 1
			ans.append([l, t[u]])
			u += 1
	pref_t = t
	i += 1
print(len(ans))
for row in ans:
	print(row[0] + 1, row[1] + 1)


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


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) = 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)


(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')
			exit(0)
		(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))


(n, k) = map(int, input().split())
d = list(map(int, input().split()))
freq = [[] for _ in range(n)]
for (idx, x) in enumerate(d):
	freq[x].append(idx + 1)
if len(freq[0]) != 1:
	print('-1')
	exit()
res = []
for i in range(1, n):
	if i != 1:
		new_k = k - 1
	else:
		new_k = k
	if len(freq[i]) > len(freq[i - 1]) * new_k:
		print('-1')
		exit()
	(prev, idx, cnt) = (freq[i - 1], 0, 0)
	for x in freq[i]:
		res.append((prev[idx], x))
		cnt += 1
		if cnt == (k if i == 1 else k - 1):
			idx += 1
			cnt = 0
print(len(res))
for (x, y) in res:
	print(x, y)


import os
import sys
import copy
(n, k) = map(lambda x: int(x), input().split())
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'])
pos = True
eg = 0
reeg = []
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
		find = False
		if vx['d'] == pd:
			vvbg = PPreidx
		else:
			vvbg = Preidx
		while vvbg < i:
			if C[d[vvbg]['idx']] < k:
				if d[vvbg]['d'] + 1 != vx['d']:
					pos = False
					break
				C[d[vvbg]['idx']] += 1
				C[vx['idx']] += 1
				eg += 1
				find = True
				reeg.append((d[vvbg]['idx'], vx['idx']))
				break
			vvbg += 1
		if not find:
			pos = False
		if i >= 1 and vx['d'] != pd:
			PPreidx = Preidx
			Preidx = i
		pd = vx['d']
if pos:
	print(eg)
	for (a, b) in reeg:
		print(a, b)
else:
	print(-1)


from sys import exit
(n, k) = 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)
			exit(0)
	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(map(lambda x: ' '.join([str(x[0]), str(x[1])]), edges)))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
d = list(map(int, input().split()))
r = [[d[i], i] for i in range(n)]
r.sort()
if r[0][0] != 0 or r[1][0] == 0:
	print(-1)
	exit()
v = [[] for i in range(n + 1)]
cnt = [0] * n
v[0].append(r[0][1])
edges = []
for (rank, ver) in r[1:]:
	if len(v[rank - 1]) == 0:
		print(-1)
		exit()
	edges.append([v[rank - 1][-1] + 1, ver + 1])
	v[rank].append(ver)
	cnt[v[rank - 1][-1]] += 1
	cnt[ver] += 1
	if cnt[v[rank - 1][-1]] == k:
		v[rank - 1].pop()
	if cnt[ver] == k:
		v[rank].pop()
print(len(edges))
for x in edges:
	print(*x)


from sys import stdin
from heapq import heappush, heappop
from collections import deque

def r():
	return stdin.readline().strip()

def r_t(tp):
	return map(tp, r().strip().split())

def r_l(tp):
	return list(r_t(tp))

def solve(n, k, d):
	(s, E, deg) = (-1, [], [0 for _ in range(n)])
	for i in range(n):
		if d[i] == 0 and s == -1:
			s = i
		elif d[i] == 0:
			return [-1]
	if s == -1:
		return [-1]
	next = []
	for u in range(n):
		if u != s:
			heappush(next, (d[u], u))
	f = [deque([]) for _ in range(n)]
	f[0].appendleft(s)
	while next:
		(dist, u) = heappop(next)
		if not f[dist - 1]:
			return [-1]
		v = f[dist - 1].pop()
		deg[v] += 1
		deg[u] += 1
		if deg[v] < k:
			f[dist - 1].appendleft(v)
		if deg[u] < k:
			f[dist].appendleft(u)
		E.append((u, v))
	return E

def main():
	(n, k) = r_t(int)
	d = r_l(int)
	ans = solve(n, k, d)
	if ans == [-1]:
		print(-1)
	else:
		print(len(ans))
		for (u, v) in ans:
			print(u + 1, v + 1)
main()


import math
import heapq
import queue

def main(arr):
	dist = {}
	for i in range(len(arr)):
		if arr[i] not in dist:
			dist[arr[i]] = []
		dist[arr[i]].append(i + 1)
	if 0 not in dist or len(dist[0]) > 1:
		print(-1)
		return
	end = max(arr) + 1
	edges = []
	for i in range(1, end):
		if i in dist:
			if i - 1 not in dist:
				print(-1)
				return
			nodes = dist[i]
			prev_len = len(dist[i - 1])
			s = 0
			for j in range(len(nodes)):
				edges.append([nodes[j], dist[i - 1][s]])
				s = (s + 1) % prev_len
	adj = {}
	for (a, b) in edges:
		if a not in adj:
			adj[a] = []
		if b not in adj:
			adj[b] = []
		(adj[a].append(b), adj[b].append(a))
	for a in adj:
		if len(adj[a]) > k:
			print(-1)
			return
	print(len(edges))
	for e in edges:
		print(*e)
	return
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
main(arr)


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()