{"problem":{"name":"[PA 2020] Skierowany graf acykliczny","description":{"content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Skierowany graf acykliczny](https://sio2.mimuw.edu.pl/c/pa-2020-1/dag/)** 正如名字所示，有向无环图（*Directed Acyclic Graph*，简称 DAG）是一个无","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9101"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Skierowany graf acykliczny](https://sio2.mimuw.edu.pl/c/pa-2020-1/dag/)**\n\n正如名字所示，有向无环图（*Directed Acyclic Graph*，简称 DAG）是一个无环的有向图。\n\n如果我们在这样一个图中选择两个节点，我们可以计算出这些节点之间存在多少条不同的有向路径。如果其中一条路径包含一条边而另一条不包含这条边，我们就认为这两条路径是不同的。\n\n你的任务是构造一个 $n$ 个节点（编号从 $1$ 到 $n$）的有向无环图，其中从节点 $1$ 到节点 $n$ 正好有 $k$ 条路径。你的图最多可以有 $100$ 个节点，每个节点最多可以有两条出边，而且不能包含重边（即如果一个节点有两条出边，它们必须通向不同的节点）。可以证明，对于每一个满足输入中约束条件的 $k$，都可以构造一个满足条件的图。\n\n## Input\n\n一行一个整数 $k$。\n\n## Output\n\n第一行输出一个整数 $n$，表示你构造的图中节点的个数。\n\n接下来 $n$ 行，每行两个整数。第 $i$ 行表示以编号为 $i$ 的节点为起点的出边到达的节点编号。这两个数中任何一个都可以是 $-1$，表示不存在这条边。如果两个数都不是 $-1$，那这两个数不应该相等。\n\n如果有许多满足条件的图，你可以输出任何一个。注意你不需要最小化节点个数，且在限制之下图节点个数是足够的。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n下图展示了输出中 $6$ 个节点的有向无环图，从 $1$ 到 $6$ 有三条路径：$1\\to 3\\to 2\\to 6,1\\to 3\\to 6$ 和 $1\\to 5\\to 6$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hinzei5g.png)\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据，保证 $1\\le k\\le 10^9$，$2\\le n\\le 100$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9101","tags":["2020","Special Judge","构造","PA（波兰）"],"sample_group":[["3","6\n3 5\n6 -1\n2 6\n2 6\n6 -1\n-1 -1"]],"created_at":"2026-03-03 11:09:25"}}