{"problem":{"name":"E. Tree Constructing","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1003E"},"statements":[{"statement_type":"Markdown","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).\n\n## Input\n\nThe first line of the input contains three integers $n$, $d$ and $k$ ($1 \\le n, d, k \\le 4 \\cdot 10^5$).\n\n## Output\n\nIf 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\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 lt.eq n, d, k lt.eq 4 dot.op 10^5$）。\n\n## Output\n\n如果不存在满足上述条件的树，请仅输出一个单词 \"_NO_\"（不含引号）。否则，第一行输出 \"_YES_\"（不含引号），然后输出 $n - 1$ 行，描述满足上述条件的树的边。树的顶点编号必须为 $1$ 到 $n$。你可以任意顺序输出边以及边连接的顶点。如果有多个答案，输出任意一个即可。1\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1003E","tags":["constructive algorithms","graphs"],"sample_group":[["6 3 3","YES\n3 1\n4 1\n1 2\n5 2\n2 6"],["6 2 3","NO"],["10 4 3","YES\n2 9\n2 10\n10 3\n3 1\n6 10\n8 2\n4 3\n5 6\n6 7"],["8 5 3","YES\n2 5\n7 2\n3 7\n3 1\n1 6\n8 7\n4 3"]],"created_at":"2026-03-03 11:00:39"}}