← 返回题目列表

Codeforces · 1003/E

E. 树的构建

中文机器翻译题面 查看原题

给你三个整数 $$$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