P14450 [ICPC 2025 Xi'an R] Directed Acyclic Graph

给定两个整数 $n$ 和 $m$，你需要构造一张有向无环图（DAG）$G = (V, E)$，其中包含恰好 $n$ 个顶点和 $m$ 条边。 在图 $G$ 中，如果从顶点 $u$ 出发存在一条路径到达顶点 $v$，则称顶点 $v$ **可达**于顶点 $u$。 对于一个非空顶点集合 $A \subseteq V$，如果存在顶点 $w$ 能够从 $A$ 中的**每一个**顶点到达，则称 $w$ 对于集合 $A$ 是 **良好** 的。记 $f(A)$ 为对集合 $A$ 来说所有 **良好** 顶点组成的集合。 你构造的图必须满足以下两个条件： - 对于每个顶点 $i$（$1 \leq i \leq n$），它都必须是从顶点 $1$ **可达** 的。 - 存在 $k$ 个两两不同的非空顶点集合 $S_1, S_2, \ldots, S_k$，使得 $f(S_1), f(S_2), \ldots, f(S_k)$ 两两不同。注意，$f(S_i)$ 允许为空。 为了证明你构造的图 $G$ 满足上述第二条条件，你还需要输出这 $k$ 个集合 $S_1, S_2, \ldots, S_k$。

输入仅一行，包含三个整数 $n, m, k$。 本题中仅有 $2$ 个测试数据： - $n = 5$, $m = 6$, $k = 6$； - $n = 100$, $m = 128$, $k = 16\,000$。

输出前 $m$ 行描述你构造的图 $G$。每一行包含两个整数 $u, v$，表示图中的一条边，从 $u$ 指向 $v$。 接下来输出 $k$ 行，描述你给出的 $k$ 个顶点集合。第 $i$ 行首先输出集合 $S_i$ 的大小，然后输出该集合中的各个顶点。

在示例中，输出构造了一张有 $n = 5$ 个顶点、$m = 6$ 条边的图。对应的 $k = 6$ 个集合为： $S_1 = \{1\},\ S_2 = \{2\},\ S_3 = \{3\},\ S_4 = \{4\},\ S_5 = \{5\},\ S_6 = \{2, 3\}$。 其中，从 $S_6 = \{2, 3\}$ 的任一顶点出发，都可以到达顶点 $4$ 和 $5$，因此有 $f(\{2, 3\}) = \{4, 5\}$。 结合： - $f(S_1) = \{1, 2, 3, 4, 5\}$ - $f(S_2) = \{2, 4, 5\}$ - $f(S_3) = \{3, 4, 5\}$ - $f(S_4) = \{4\}$ - $f(S_5) = \{5\}$ - $f(S_6) = \{4, 5\}$ 可以看到这些集合两两不同，满足题目要求。 :::align{center}  ::: 翻译由 ChatGPT-5 完成