Tree Constructing
Contest: Codeforces Round 494 (Div. 3)
Difficulty rating: 2100
Tags: constructive algorithms, graphs

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 format:
The first line of the input contains three integers $$$n$$$, $$$d$$$ and $$$k$$$ ($$$1 \le n, d, k \le 4 \cdot 10^5$$$).

Output format:
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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
6 3 3

Example output:
YES
3 1
4 1
1 2
5 2
2 6

Example input:
6 2 3

Example output:
NO

Editorial:
Let's construct a tree by the following algorithm: if $$$d \ge n$$$, let's print "NO" and terminate the program. Otherwise let's keep the array $$$deg$$$ of the length $$$n$$$ which will represent degrees of vertices.
The first step is to construct the diameter of the tree. Let first $$$d + 1$$$ vertices form it. Let's add $$$d$$$ edges to the answer, increase degrees of vertices corresponding to this edges, and if some vertex has degree greater than $$$k$$$, print "NO" and terminate the program.
The second (and the last) step is to attach the remaining $$$n - d - 1$$$ vertices to the tree. Let's call the vertex free if its degree is less than $$$k$$$. Also let's keep all free vertices forming the diameter in some data structure which allows us to take the vertex with the minimum maximal distance to any other vertex and remove such vertices. It can be done by, for example, set of pairs ($$$dist_v, v$$$), where $$$dist_v$$$ is a maximum distance from the vertex $$$v$$$ to any other vertex. Now let's add all vertices from starting from the vertex $$$d + 1$$$ (0-indexed) to the vertex $$$n - 1$$$, let the current vertex be $$$u$$$. We get the vertex with the minimum maximal distance to any other vertex, let it be $$$v$$$. Now we increase the degree of vertices $$$u$$$ and $$$v$$$, add the edge between they, and if $$$v$$$ still be free, return it to the data structure, otherwise remove it. The same with the vertex $$$u$$$ (it is obvious that its maximal distance to any other vertex will be equals $$$dist_v + 1$$$).
If at any step our data structure will be empty or the minimum maximal distance will be equals $$$d$$$, the answer is "NO". Otherwise we can print the answer. See my solution to better understanding.
Overall complexity: $$$O(n \log n)$$$ or $$$O(n)$$$ (depends on implementation).