给你三个整数 $$$n$$$、$$$d$$$ 和 $$$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.
无向树是具有 $$$n - 1$$$ 边的连通无向图。
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$$$ ($$$1 \le n, d, k \le 4 \cdot 10^5$$$)。
输出
如果没有满足上述条件的树,则仅打印一个单词“NO”(不带引号)。
Otherwise in the first line print "YES" (without quotes), and then print $$$n - 1$$$ lines describing edges of a tree satisfying the conditions above.树的顶点必须从 $$$1$$$ 到 $$$n$$$ 进行编号。您可以按任意顺序打印边和由边连接的顶点。如果有多个答案,请打印其中任何一个。1
示例
输入 #1
6 3 3
输出 #1
YES 3 1 4 1 1 2 5 2 2 6
输入 #2
6 2 3
输出 #2
NO
输入 #3
10 4 3
输出 #3
YES 2 9 2 10 10 3 3 1 6 10 8 2 4 3 5 6 6 7
输入#4
8 5 3
输出#4
YES 2 5 7 2 3 7 3 1 1 6 8 7 4 3