You are given three integers $n$, $d$ and $k$.

Your task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible.

An undirected tree is a connected undirected graph with $n - 1$ edges.

Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.

Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex $u$ it is the number of edges $(u, v)$ that belong to the tree, where $v$ is any other vertex of a tree).


-----Input-----

The first line of the input contains three integers $n$, $d$ and $k$ ($1 \le n, d, k \le 4 \cdot 10^5$).


-----Output-----

If there is no tree satisfying the conditions above, print only one word "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes), and then print $n - 1$ lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from $1$ to $n$. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1


-----Examples-----
Input
6 3 3

Output
YES
3 1
4 1
1 2
5 2
2 6

Input
6 2 3

Output
NO

Input
10 4 3

Output
YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7

Input
8 5 3

Output
YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3

Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms
Expected Time Complexity: O(N^2)

Starter code:

Solutions:
def main():
	(n, d, k) = map(int, input().split())
	if n < d + 1 or (d > 1 and k == 1):
		print('NO')
		return
	edges = [(1, 2)]
	stack = []
	d2 = d / 2
	d21 = d2 + 1
	for node in range(2, d + 1):
		edges.append((node, node + 1))
		stack.append([node, d2 - abs(d21 - node), k - 2])
	next_i = d + 2
	while next_i <= n:
		if not stack:
			print('NO')
			return
		node = stack[-1]
		(i, remaining_depth, remaining_degree) = node
		if remaining_depth == 0 or remaining_degree == 0:
			stack.pop()
			continue
		node[2] -= 1
		edges.append((i, next_i))
		stack.append([next_i, remaining_depth - 1, k - 1])
		next_i += 1
	print('YES')
	print('\n'.join(('{} {}'.format(a, b) for (a, b) in edges)))
main()


from collections import deque
(n, d, k) = map(int, input().split())
if n == 1:
	print('NO')
	return
if n == 2:
	if d > 1:
		print('NO')
	else:
		print('YES')
		print(1, 2)
	return
if not 2 <= d <= n - 1 or k == 1:
	print('NO')
	return
ans = []
for i in range(d):
	ans.append((i + 1, i + 2))
now = d + 2
for i in range(d - 1):
	q = deque([(i + 2, min(i, d - i - 2))])
	first = True
	while q and len(ans) < n - 1:
		(node, depth) = q.popleft()
		end = now + k - 1
		if first:
			end -= 1
		for j in range(now, end):
			ans.append((node, j))
			if len(ans) == n - 1:
				break
			if depth > 0:
				q.append((j, depth - 1))
		now = end
		first = False
if len(ans) == n - 1:
	print('YES')
	for (i, j) in ans:
		print(i, j)
else:
	print('NO')


import sys
input = sys.stdin.readline

def main():
	a = input().split(' ')
	n = int(a[0])
	d = int(a[1])
	k = int(a[2])
	if d > n - 1:
		sys.stdout.write('NO\n')
		return
	par = [-1 for i in range(n)]
	prevlevel = [0]
	bad = [False for i in range(n)]
	clevel = []
	cdep = 1
	callow = k
	cnode = 1
	firstchild = 1
	for i in range(1, n):
		if len(clevel) == callow:
			prevlevel = clevel
			clevel = []
			cdep += 1
			callow *= k - 1
			firstchild *= k - 1
		cdiv = k
		if cdep > 1:
			cdiv -= 1
		if cdiv == 0:
			sys.stdout.write('NO\n')
			return
		par[cnode] = prevlevel[len(clevel) // cdiv]
		clevel.append(cnode)
		cnode += 1
	mdep = d // 2
	if cdep > mdep + 1:
		sys.stdout.write('NO\n')
		return
	if cdep == mdep + 1 and d % 2 == 0:
		sys.stdout.write('NO\n')
		return
	if cdep == mdep + 1 and len(clevel) > firstchild:
		sys.stdout.write('NO\n')
		return
	attach1 = -1
	attach2 = -1
	d1 = cdep
	d2 = cdep
	attach1 = clevel[0]
	if len(clevel) > firstchild:
		attach2 = clevel[-1]
	else:
		attach2 = prevlevel[-1]
		d2 -= 1
	te = attach1
	while te != -1:
		bad[te] = True
		te = par[te]
	te = attach2
	while te != -1:
		bad[te] = True
		te = par[te]
	cptr = n - 1
	while d1 + d2 < d:
		if bad[cptr]:
			cptr -= 1
			continue
		if d2 < d1:
			par[cptr] = attach2
			attach2 = cptr
			d2 += 1
		else:
			par[cptr] = attach1
			attach1 = cptr
			d1 += 1
		cptr -= 1
	sys.stdout.write('YES\n')
	for i in range(1, n):
		sys.stdout.write(str(i + 1) + ' ' + str(par[i] + 1) + '\n')
main()


(n, d, k) = map(int, input().split())
num = d + 2

def solve():
	nonlocal num
	if n == 1:
		return 'NO'
	if n == 2:
		if d != 1:
			return 'NO'
		else:
			return 'YES\n1 2'
	if k < 2:
		return 'NO'
	if d > n - 1:
		return 'NO'
	depth = [min(i, d - i) for i in range(d + 1)]
	ans = [(i + 1, i + 2) for i in range(d)]

	def dfs(v, depth):
		nonlocal num
		if depth == 0:
			return
		for i in range(k - 1):
			if len(ans) == n - 1:
				return
			v2 = num
			num += 1
			ans.append((v, v2))
			dfs(v2, depth - 1)
	for v in range(d + 1):
		if depth[v] == 0:
			continue
		for i in range(k - 2):
			if len(ans) == n - 1:
				break
			v2 = num
			num += 1
			ans.append((v + 1, v2))
			if depth[v] > 1:
				dfs(v2, depth[v] - 1)
	if len(ans) < n - 1:
		return 'NO'
	return 'YES\n%s' % '\n'.join(['%d %d' % i for i in ans])
print(solve())


def main():
	(n, d, k) = list(map(int, input().split()))
	if n == 2 and d == 1 and (k == 1):
		print('YES')
		print('1 2')
		return 0
	if n == d + 1 and k - 1:
		print('YES')
		for i in range(1, d + 1):
			print(i, i + 1)
		return 0
	if n < d + 1 or k <= 2 or d == 1:
		print('NO')
		return 0
	if d % 2 == 0:
		if n * (k - 2) > -2 + k * (k - 1) ** (d // 2):
			print('NO')
			return 0
		print('YES')
		for i in range(1, d + 1):
			print(i, i + 1)
		nodes = d + 1
		leaves = [1 + d // 2]
		dev = 0
		while True:
			new_leaves = []
			for i in leaves:
				for j in range(k - 1 - (i <= d + 1)):
					nodes += 1
					print(i, nodes)
					new_leaves.append(nodes)
					if nodes == n:
						return 0
			dev += 1
			leaves = new_leaves + [1 - dev + d // 2, 1 + dev + d // 2]
	else:
		if n * (k - 2) > -2 + k * (k - 1) ** (d // 2) + (k - 2) * (k - 1) ** (d // 2):
			print('NO')
			return 0
		print('YES')
		for i in range(1, d + 1):
			print(i, i + 1)
		nodes = d + 1
		leaves = [1 + d // 2, 2 + d // 2]
		dev = 0
		while True:
			new_leaves = []
			for i in leaves:
				for j in range(k - 1 - (i <= d + 1)):
					nodes += 1
					print(i, nodes)
					new_leaves.append(nodes)
					if nodes == n:
						return 0
			dev += 1
			leaves = new_leaves + [1 - dev + d // 2, 2 + dev + d // 2]
main()


(n, d, k) = [int(x) for x in input().strip().split(' ')]
l = []
i = 1
if n <= d:
	print('NO')
elif k == 1:
	if n > 2:
		print('NO')
	elif n == 2:
		print('YES')
		print(1, 2)
else:
	n += 1
	flag = False
	while i < min(d + 1, n):
		l.append(str(i) + ' ' + str(i + 1))
		i += 1
	i += 1
	cnt1 = 0
	cnt2 = 1
	se = [[2, d + 1, 1]]
	while cnt1 < cnt2:
		start = se[cnt1][0]
		end = se[cnt1][1]
		mode = se[cnt1][2]
		kk = 3
		while i < n and kk <= k:
			if i < n and (not flag):
				j = start
				while i < n and j < end:
					if mode == 1:
						c = min(j - start + 1, end - j)
					else:
						c = min(end - j, d - end + j)
					if c > 1:
						se.append([i, i + c - 1, 2])
						cnt2 += 1
					ki = j
					while i < n and c > 0:
						l.append(str(ki) + ' ' + str(i))
						c -= 1
						ki = i
						i += 1
					j += 1
			else:
				flag = True
				break
			kk += 1
		cnt1 += 1
	if i < n or flag:
		print('NO')
	else:
		print('YES')
		print('\n'.join(l))


from sys import exit

def bad():
	print('NO')
	exit()
node = 1

def make_branch(u, d, deg, g, n, k):
	global node
	while deg[u] < k and d > 0 and (node < n):
		node += 1
		deg[u] += 1
		deg[node] = 1
		g[u].append(node)
		make_branch(node, d - 1, deg, g, n, k)

def main():
	global node
	(n, d, k) = map(int, input().split())
	if d >= n or (k == 1 and n > 2):
		bad()
	g = [[] for _ in range(n + 5)]
	deg = [0 for _ in range(n + 5)]
	for i in range(1, d + 1):
		g[i].append(i + 1)
		deg[i] += 1
		deg[i + 1] += 1
	node = d + 1
	LD = 1
	RD = d - 1
	for u in range(2, d + 1):
		make_branch(u, min(LD, RD), deg, g, n, k)
		LD += 1
		RD -= 1
	used = [False for _ in range(n + 5)]
	q = [[1, 1]]
	used[1] = True
	while len(q) > 0:
		(u, p) = q.pop()
		for v in g[u]:
			if v != p:
				used[v] = True
				q.append([v, u])
	for i in range(1, n + 1):
		if used[i] == False:
			bad()
	print('YES')
	for u in range(1, n + 1):
		for v in g[u]:
			print(u, v)
main()


import sys
(n, d, k) = list(map(int, input().split()))
if n <= d:
	print('NO')
	return
if k == 1 and n > 2:
	print('NO')
	return
edgestot = []
edges = [[] for i in range(n)]
tovisit = []
for i in range(d):
	edgestot.append([i, i + 1])
	tovisit.append([i + 1, min(i + 1, d - i - 1)])
	edges[i].append(i + 1)
	edges[i + 1].append(i)
cur = d + 1
while cur < n and len(tovisit) > 0:
	x = tovisit.pop()
	if x[1] == 0:
		continue
	while len(edges[x[0]]) < k and cur < n:
		tovisit.append([cur, x[1] - 1])
		edgestot.append([cur, x[0]])
		edges[x[0]].append(cur)
		edges[cur].append(x[0])
		cur += 1
if len(edgestot) == n - 1:
	print('YES')
	for i in range(n - 1):
		print(edgestot[i][0] + 1, edgestot[i][1] + 1)
else:
	print('NO')


from bisect import bisect_left, bisect_right, insort
from collections import Sequence, MutableSequence
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, list(zip(head, tail))))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, list(zip(head, tail))))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = list(range(start, stop, step))
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				if start_pos == stop_pos:
					return _lists[start_pos][start_idx:stop_idx]
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = list(range(start, stop, step))
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(list(map(reversed, reversed(self._lists))))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(list(range(min_idx, max_idx)))
				return list(map(_lists[min_pos].__getitem__, indices))
			indices = list(range(min_idx, max_idx))
			return list(map(_lists[min_pos].__getitem__, indices))
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = list(range(min_idx, len(_lists[min_pos])))
				max_indices = list(range(max_idx))
				return chain(list(map(_lists[max_pos].__getitem__, reversed(max_indices))), list(map(_lists[min_pos].__getitem__, reversed(min_indices))))
			min_indices = list(range(min_idx, len(_lists[min_pos])))
			max_indices = list(range(max_idx))
			return chain(list(map(_lists[min_pos].__getitem__, min_indices)), list(map(_lists[max_pos].__getitem__, max_indices)))
		if reverse:
			min_indices = list(range(min_idx, len(_lists[min_pos])))
			sublist_indices = list(range(next_pos, max_pos))
			sublists = list(map(_lists.__getitem__, reversed(sublist_indices)))
			max_indices = list(range(max_idx))
			return chain(list(map(_lists[max_pos].__getitem__, reversed(max_indices))), chain.from_iterable(list(map(reversed, sublists))), list(map(_lists[min_pos].__getitem__, reversed(min_indices))))
		min_indices = list(range(min_idx, len(_lists[min_pos])))
		sublist_indices = list(range(next_pos, max_pos))
		sublists = list(map(_lists.__getitem__, sublist_indices))
		max_indices = list(range(max_idx))
		return chain(list(map(_lists[min_pos].__getitem__, min_indices)), chain.from_iterable(sublists), list(map(_lists[max_pos].__getitem__, max_indices)))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			import sys
			import traceback
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value
(n, d, k) = list(map(int, input().split()))
if d >= n:
	print('NO')
else:
	deg = [0] * n
	ans = []
	free = SortedList()
	for i in range(d):
		deg[i] += 1
		deg[i + 1] += 1
		if deg[i] > k or deg[i + 1] > k:
			print('NO')
			return
		ans.append((i, i + 1))
	for i in range(1, d):
		free.add((max(i, d - i), i))
	for i in range(d + 1, n):
		while len(free) > 0 and deg[free[0][1]] == k:
			free.pop(0)
		if len(free) == 0 or free[0][0] == d:
			print('NO')
			return
		deg[i] += 1
		deg[free[0][1]] += 1
		ans.append((i, free[0][1]))
		free.add((free[0][0] + 1, i))
	print('YES')
	for elem in ans:
		print(elem[0] + 1, elem[1] + 1)


(n, d, k) = map(int, input().split())
if n == 1:
	print('NO')
	return
if k == 1:
	if n == 2 and d == 1:
		print('YES')
		print(1, 2)
	else:
		print('NO')
	return
if n < d + 1:
	print('NO')
	return
co = 1
ans = []
for i in range(1, d + 1):
	ans.append((i, i + 1))
	co += 1

def dfs(r, dist, co):
	if 2 <= r <= d:
		t = k - 2
	else:
		t = k - 1
	if co == n:
		return co
	for _ in range(t):
		if dist == d:
			return co
		if co == n:
			return co
		co += 1
		ans.append((r, co))
		co = dfs(co, dist + 1, co)
	return co
for i in range(2, d + 1):
	co = dfs(i, max(i - 1, d - i + 1), co)
if co == n:
	print('YES')
	for j in ans:
		print(*j)
else:
	print('NO')


def main():
	(n, d, k) = list(map(int, input().split()))
	(r, odd) = divmod(d, 2)
	k -= 1
	cap = d + 1 if k == 1 else 1
	if k > 1:
		cap = 2 * (k ** (r + 1) - 1) // (k - 1) if odd else 1 + (k + 1) * (k ** r - 1) // (k - 1)
	if n == 1 or k < 1 < n - 1 or (k == 1 and d != n - 1) or (d >= n) or (k > 1 and (not d < n <= cap)):
		print('NO')
		return

	def dfs(parent, depth):
		stack = []
		for _ in range(k - 1):
			child = rest.pop()
			res.append('%s %s' % (parent, child))
			if depth:
				stack.append((child, depth))
		while stack:
			(parent, depth) = stack.pop()
			depth -= 1
			for _ in range(k):
				child = rest.pop()
				res.append('%s %s' % (parent, child))
				if depth:
					stack.append((child, depth))
	res = ['YES']
	for pc in enumerate(list(range(2, d + 2)), 1):
		res.append('%d %d' % pc)
	rest = list(range(n, d + 1, -1))
	try:
		for p in range(r + 1, r + odd + 2):
			dfs(p, r - 1)
		for (de, p, q) in zip(list(range(r - 2, -1, -1)), list(range(r, 1, -1)), list(range(r + odd + 2, d + 1))):
			dfs(p, de)
			dfs(q, de)
	except IndexError:
		pass
	print('\n'.join(res))

def __starting_point():
	main()
__starting_point()


(n, d, k) = list(map(int, input().split()))
if d + 1 > n:
	print('NO')
	return
ans = []
dist = [0] * n
deg = [0] * n
for i in range(d + 1):
	if i == 0 or i == d:
		deg[i] = 1
	else:
		deg[i] = 2
	if i != d:
		ans.append((i + 1, i + 2))
	dist[i] = max(i, d - i)
for i in range(n):
	if deg[i] > k:
		print('NO')
		return
from collections import deque
q = deque(list(range(d + 1)))
cur = d + 1
while q and cur < n:
	v = q.pop()
	if dist[v] < d and deg[v] < k:
		deg[v] += 1
		dist[cur] = dist[v] + 1
		deg[cur] = 1
		ans.append((v + 1, cur + 1))
		q.append(v)
		q.append(cur)
		cur += 1
	else:
		continue
if cur != n:
	print('NO')
else:
	print('YES')
	for i in range(len(ans)):
		print(*ans[i])


import sys

def pprint(s):
	sys.stdout.write(str(s) + '\n')

def solve(n, d, k):
	for i in range(1, d + 1):
		pprint(str(i) + ' ' + str(i + 1))
		if i + 1 == n:
			exit()
	q = d + 2
	for i in range(2, d + 1):
		for j in range(k - 2):
			pprint(str(i) + ' ' + str(q))
			if q == n:
				exit()
			q += 1

			def rec(depth, current, head):
				if depth == 0:
					return current
				for i in range(k - 1):
					pprint(str(head) + ' ' + str(current))
					if current == n:
						exit()
					current += 1
					current = rec(depth - 1, current, current - 1)
				return current
			if i <= (d + 2) / 2:
				depth = i - 2
			else:
				depth = d - i
			q = rec(depth, q, q - 1)
(n, d, k) = map(int, input().split())
q = k - 1
maxi = 0
if k == 2:
	maxi = d + 1
elif d % 2:
	maxi = (q * (1 - q ** (d // 2)) // (1 - q) + 1) * 2
else:
	maxi = (q * (1 - q ** (d // 2 - 1)) // (1 - q) + 1) * 3 + 1
if d == 2:
	maxi = k + 1
if n > maxi or n <= d:
	print('NO')
else:
	print('YES')
	solve(n, d, k)


def construct_tree(n, d, k):
	nodes = []
	edges = []
	if d > n - 1:
		return None
	if k == 1 and n > 2:
		return None
	for i in range(1, d + 2):
		current_deg = k - 1 if i == 1 or i == d + 1 else k - 2
		current_depth = min(i - 1, d - i + 1)
		if current_depth and current_deg:
			nodes.append([i, min(i - 1, d - i + 1), current_deg])
		if i < d + 1:
			edges.append([i, i + 1])
	current_nodes_count = d + 2
	pos = 0
	while current_nodes_count < n + 1:
		if pos >= len(nodes):
			return None
		current = nodes[pos]
		if not current[2]:
			pos += 1
			if pos == len(nodes):
				break
			continue
		if current[1] - 1 and k - 1:
			nodes.append([current_nodes_count, current[1] - 1, k - 1])
		edges.append([current[0], current_nodes_count])
		current[2] -= 1
		current_nodes_count += 1
	if current_nodes_count == n + 1:
		return edges
	return None
(n, d, k) = [int(val) for val in input().split()]
edges = construct_tree(n, d, k)
if edges:
	print('YES')
	print('\n'.join(['{0} {1}'.format(e[0], e[1]) for e in edges]))
else:
	print('NO')


(n, d, k) = map(int, input().strip().split())
ans = []
if d > n - 1:
	print('NO')
	exit(0)
if k < 2 and n > 2:
	print('NO')
	exit(0)
l1 = [0 for i in range(d + 2)]
count = d
cnt = d + 2

def insert(par, v, r, e):
	global count
	global cnt
	if count == n - 1:
		print('YES')
		for o in ans:
			print(o[0], o[1])
		exit(0)
	else:
		ans.append([par, v])
		cnt = cnt + 1
		count = count + 1
	if e == 0:
		return
	while r != 0:
		insert(v, cnt, k - 1, e - 1)
		r = r - 1
	return
for i in range(1, d + 1):
	ans.append([i, i + 1])
for i in range(1, d + 2):
	l1[i] = min(i - 1, d + 1 - i)
for i in range(2, d + 1):
	r = k - 2
	while r != 0:
		insert(i, cnt, k - 1, l1[i] - 1)
		r = r - 1
if count < n - 1:
	print('NO')
else:
	print('YES')
	for o in ans:
		print(o[0], o[1])
	exit(0)


def main():
	(n, d, k) = list(map(int, input().split()))
	_min = d + 1
	if n < _min:
		print('NO')
	else:
		res = []
		deg = [0] * (n + 1)
		dist = [0] * (n + 1)
		stack = []
		deg[1] = 1
		for i in range(1, d + 1):
			res.append((i, i + 1))
			if i > 1:
				deg[i] += 2
			dist[i] = max(i - 1, d + 1 - i)
		dist[d + 1] = d
		deg[d + 1] = 1
		for i in range(2, d + 1):
			stack.append(i)
		next = d + 2
		while stack:
			if next > n:
				break
			v = stack.pop()
			if dist[v] < d:
				while next <= n and deg[v] < k:
					res.append((v, next))
					deg[v] += 1
					deg[next] += 1
					dist[next] = dist[v] + 1
					if dist[next] < d:
						stack.append(next)
					next += 1
		ok = next > n
		ok &= all((deg[i] <= k for i in range(1, n + 1)))
		ok &= all((dist[i] <= d for i in range(1, n + 1)))
		if not ok:
			print('NO')
		else:
			print('YES')
			for e in res:
				print(*e)

def __starting_point():
	main()
__starting_point()


def bad():
	print('NO')
	return
node = 1

def make_branch(u, d, deg, g, n, k):
	nonlocal node
	while deg[u] < k and d > 0 and (node < n):
		node += 1
		deg[u] += 1
		deg[node] = 1
		g[u].append(node)
		make_branch(node, d - 1, deg, g, n, k)

def main():
	nonlocal node
	(n, d, k) = list(map(int, input().split()))
	if d >= n or (k == 1 and n > 2):
		bad()
	g = [[] for _ in range(n + 5)]
	deg = [0 for _ in range(n + 5)]
	for i in range(1, d + 1):
		g[i].append(i + 1)
		deg[i] += 1
		deg[i + 1] += 1
	node = d + 1
	LD = 1
	RD = d - 1
	for u in range(2, d + 1):
		make_branch(u, min(LD, RD), deg, g, n, k)
		LD += 1
		RD -= 1
	used = [False for _ in range(n + 5)]
	q = [[1, 1]]
	used[1] = True
	while len(q) > 0:
		(u, p) = q.pop()
		for v in g[u]:
			if v != p:
				used[v] = True
				q.append([v, u])
	for i in range(1, n + 1):
		if used[i] == False:
			bad()
	print('YES')
	for u in range(1, n + 1):
		for v in g[u]:
			print(u, v)
main()


import sys
input = sys.stdin.buffer.readline
from collections import deque
(n, d, k) = map(int, input().split())
if d >= n:
	print('NO')
	exit()
graph = [[] for i in range(n + 1)]
for i in range(1, d + 2):
	graph[i].append(min(i - 1, d + 1 - i))
for i in range(1, d + 1):
	graph[i].append(i + 1)
	graph[i + 1].append(i)
deg = [0] * (n + 1)
deg[1] = 1
deg[d + 1] = 1
for i in range(2, d + 1):
	deg[i] = 2
for i in deg:
	if i > k:
		print('NO')
		exit()
p = d + 2
for i in range(1, d + 2):
	q = deque()
	q.append(i)
	while len(q) != 0:
		x = q.popleft()
		while graph[x][0] > 0 and deg[x] < k and (p <= n):
			graph[x].append(p)
			deg[x] = deg[x] + 1
			graph[p].append(graph[x][0] - 1)
			graph[p].append(x)
			deg[p] = deg[p] + 1
			q.append(p)
			p = p + 1
if p <= n:
	print('NO')
else:
	print('YES')
	vis = [-1] * (n + 1)
	for i in range(1, d + 2):
		if vis[i] == -1:
			q = deque()
			q.append(i)
			while len(q) != 0:
				x = q.popleft()
				vis[x] = 1
				for j in range(1, len(graph[x])):
					if vis[graph[x][j]] == -1:
						print(x, graph[x][j])
						q.append(graph[x][j])