CF1003E.Tree Constructing

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

给你三个整数 $n$、$d$ 和 $k$。

你的任务是构造一棵包含 $n$ 个顶点的无向树，使其直径为 $d$，且每个顶点的度数至多为 $k$；如果无法构造，则说明这是不可能的。

无向树是一种具有 $n - 1$ 条边的连通无向图。

树的直径是指该树中所有顶点对之间简单路径（即路径中每个顶点至多出现一次）的最大长度。

顶点的度数是指与该顶点关联的边的数量（即对于顶点 $u$，它是属于该树的所有边 $(u, v)$ 的数量，其中 $v$ 是树中任意其他顶点）。

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

输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 \le n, d, k \le 4 \cdot 10^5$）。

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

如果不存在满足上述条件的树，则仅输出一个单词 “NO”（不带引号）。

否则，第一行输出 “YES”（不带引号），然后输出 $n - 1$ 行，每行描述一棵满足上述条件的树的一条边。树的顶点编号必须为 $1$ 到 $n$。你可以以任意顺序输出各条边，以及每条边所连接的两个顶点。若存在多个合法答案，输出任意一个即可。