{"raw_statement":[{"iden":"statement","content":"You are given three integers $n$, $d$ and $k$.\n\nYour 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\nAn undirected tree is a connected undirected graph with $n - 1$ edges.\n\nDiameter 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.\n\nDegree 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)."},{"iden":"input","content":"The first line of the input contains three integers $n$, $d$ and $k$ ($1 \\le n, d, k \\le 4 \\cdot 10^5$)."},{"iden":"output","content":"If there is no tree satisfying the conditions above, print only one word \"_NO_\" (without quotes).\n\nOtherwise 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"},{"iden":"examples","content":"Input\n\n6 3 3\n\nOutput\n\nYES\n3 1\n4 1\n1 2\n5 2\n2 6\n\nInput\n\n6 2 3\n\nOutput\n\nNO\n\nInput\n\n10 4 3\n\nOutput\n\nYES\n2 9\n2 10\n10 3\n3 1\n6 10\n8 2\n4 3\n5 6\n6 7\n\nInput\n\n8 5 3\n\nOutput\n\nYES\n2 5\n7 2\n3 7\n3 1\n1 6\n8 7\n4 3"}],"translated_statement":[{"iden":"statement","content":"给定三个整数 $n$、$d$ 和 $k$。\n\n你的任务是构造一棵包含 $n$ 个顶点的无向树，使其直径为 $d$，且每个顶点的度数不超过 $k$；若不可能，则指出不可能。\n\n无向树是一个具有 $n - 1$ 条边的连通无向图。\n\n树的直径是该树中所有顶点对之间最简单路径（每个顶点至多出现一次的路径）的最大长度。\n\n顶点的度数是指与该顶点相连的边的数量（即对于顶点 $u$，它是属于树的边 $(u, v)$ 的数量，其中 $v$ 是树中的任意其他顶点）。\n\n输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 lt.eq n, d, k lt.eq 4 dot.op 10^5$）。\n\n如果不存在满足上述条件的树，请仅输出一个单词 \"_NO_\"（不含引号）。\n\n否则，第一行输出 \"_YES_\"（不含引号），然后输出 $n - 1$ 行，描述满足上述条件的树的边。树的顶点编号必须为 $1$ 到 $n$。你可以任意顺序输出边以及边连接的顶点。如果有多个答案，输出任意一个即可。1\n\n"},{"iden":"input","content":"输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 lt.eq n, d, k lt.eq 4 dot.op 10^5$）。"},{"iden":"output","content":"如果不存在满足上述条件的树，请仅输出一个单词 \"_NO_\"（不含引号）。否则，第一行输出 \"_YES_\"（不含引号），然后输出 $n - 1$ 行，描述满足上述条件的树的边。树的顶点编号必须为 $1$ 到 $n$。你可以任意顺序输出边以及边连接的顶点。如果有多个答案，输出任意一个即可。1"},{"iden":"examples","content":"输入\n6 3 3\n输出\nYES\n3 1\n4 1\n1 2\n5 2\n2 6\n\n输入\n6 2 3\n输出\nNO\n\n输入\n10 4 3\n输出\nYES\n2 9\n2 10\n10 3\n3 1\n6 10\n8 2\n4 3\n5 6\n6 7\n\n输入\n8 5 3\n输出\nYES\n2 5\n7 2\n3 7\n3 1\n1 6\n8 7\n4 3"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, d, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, d, k \\leq 4 \\cdot 10^5 $.  \n\nLet $ T = (V, E) $ be an undirected tree with:  \n- $ |V| = n $,  \n- $ |E| = n - 1 $,  \n- Diameter $ \\mathrm{diam}(T) = d $,  \n- $ \\deg(v) \\leq k $ for all $ v \\in V $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 4 \\cdot 10^5 $  \n2. $ 1 \\leq d \\leq 4 \\cdot 10^5 $  \n3. $ 1 \\leq k \\leq 4 \\cdot 10^5 $  \n\n**Objective**  \nDetermine whether there exists a tree $ T $ satisfying:  \n- $ \\mathrm{diam}(T) = d $,  \n- $ \\max_{v \\in V} \\deg(v) \\leq k $.  \n\nIf such a tree exists, output:  \n- \"YES\", followed by $ n - 1 $ edges (as pairs of vertices).  \nOtherwise, output:  \n- \"NO\".","simple_statement":null,"has_page_source":false}