小可可需要你构造一个 n 个点 m 条边且无重边的有向无环图（节点从 1 开始标 号），其中点 1 的入度和点 n 的出度必须为 0。并且，对于 0 \sim p 中的每一个整数 i，都能通过保留图中的一部分有向边使得从点 1 到点 n 的不同路径方案数为 i。请给出你构造的有向无环图以及对于每一个 i 需要保留哪些边。

答案不唯一，因此你只需输出任意一种可行方案，详见输出格式。你可以自己指 定 n, m 的大小，但必须保证 n \le 24, m \le 65。

一条经过 |P| 个点的，从点 1 到点 n 的路径 P 可以描述为一个长度为 |P| 的序列 (P_1,P_2, …, P_{|p|})，其中 P_1 = 1, P|p| = n，并且对于 i = 1, 2, …, |P| − 1，图中都存在 P_i → P_{i+1}的有向边。 两条路径 A,B 不同，当且仅当 |A|≠|B|，或者存在一个 1 \sim |A| 中的正整数 i，使得 A_i≠B_i。

输入仅有一行一个正整数 p。

第一行输出两个正整数 n,m，表示你构造的有向无环图的点数和边数。

接下来 m 行，第 i 行输出两个正整数 u,v，表示图中的第 i 条有向边 u→v。

接下来 p+1 行，第 i 行输出一个长度为 m 的仅由 01 构成的字符串，表示要使得点 1 到点 n 的不同路径方案数为 i−1 的情况下选择保留哪些边：从左到右第 j 个字符若为 1 表示保留第 j 条边，0 表示不保留。

【样例解释】

样例中 p = 3。下图是样例输出中构造出的一种可行的图。

当六条边全部不选的时候，显然点 1 无法到达点 5，方案数为 0。

仅保留第 1, 2 条边时，点 1 到点 5 仅有一条路径可选（1 → 2 → 5），方案数为 1。

保留第 1, 2, 3, 4 条边时，点 1 到点 5 有两条路径可选（1 → 2 → 5 和 1 → 3 →5），方案数为 2。

所有边全部保留时，点 1 到点 5 有三条路径可选（1 → 2 → 5，1 → 3 → 5 和 1 → 4 → 5），方案数为 3。

因此，这组构造方案是合法的。

【数据范围】

对于所有数据，保证 p ≤ 75000。

本题共计二十个测试点，每个测试点的输入是已知的（详见下表）。只有你的构造 合法，并且满足 n \le 24, m \le 65 才可获得该测试点的分数，否则该测试点不得分。

【温馨提示】 本题 p 较大时输出量较大，因此请使用合适的方式输出。你也应当使用恰当的方 法打开输出文件以防止电脑崩溃。

本题下发校验器 checker.cpp 供你测试你的构造是否合法。下发的校验器与最终 评测中使用的校验器有所不同，你也无需关心其中的具体内容。请将本题下发文件 checker.cpp 解压缩到你的本题程序所在文件夹中，并在你的本题程序所在文件夹中右键单击，选择菜单中的“在终端打开”，然后使用以下命令编译 checker.cpp：g++ checker.cpp ‐o checker ‐O2 ‐std=c++14

随后用以下命令测试你的输出：

./checker <input.in> <output.out>

其中，<input.in> 是输入文件，<output.out> 是输出文件。实际输入时不需要尖括号。你必须严格按照要求使用指令，否则将得到 Format incorrect。

以下是从 construct.in 读入，输出到 construct.out 的指令示例：

./checker construct.in construct.out

成功运行指令后，如果你的构造合法，你将会看到 Accepted，否则你会看到 Wrong answer 以及详细错误信息，具体如下：

1. Wrong answer [1]：你构造的图中点数过多（n \gt 24）。
2. Wrong answer [2]：你构造的图中边数过多（m \gt 65）。
3. Wrong answer [3]：你构造的图违反了点 1 入度为 0 的要求。
4. Wrong answer [4]：你构造的图违反了点 n 出度为 0 的要求。
5. Wrong answer [5] u v：你构造的图中出现了重边。重边是 u → v。
6. Wrong answer [6]：你构造的图不是无环图。
7. Wrong answer [7] x：你没有构造出路径数恰好为 x 的选边方案。
8. Wrong answer [8]：你输出的字符串长度不是 m。

请注意：如果你的输出不符合输出格式，校验器可能会返回无效信息或者出现运行时错误。

“科大国创杯”2026 年安徽省青少年信息学科普日活动 中学组

科大国创杯