P16533 [THUPC 2026 决赛] 社交网络

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 讨论完令人头疼的科研与审稿，茶话会的话题逐渐转向了日常的社交。小 T 兴致勃勃地分享了他的一个有趣发现：在某一常用的社交平台上，用户彼此间的关注关系恰好都是严格的**单向关注**，即不存在两名用户互相关注的情况。 > > 这个奇妙的现象立刻引起了大家的讨论。小 S 顺势提取了该网络的部分统计数据，收集到了每位用户的关注数与粉丝数。遗憾的是，她在传阅数据的过程中不小心弄丢了一部分，最后只留下了一个由若干正整数构成的集合。小 S 发现，对于集合中的每一个元素，总能找到至少一个用户，其关注数或粉丝数恰好等于该元素。 > > 由于平台完整的关注结构对外保密，具体的社交关系网已无从知晓。为了验证这些残存数据的合理性，大家纷纷拿起了纸笔，尝试着还原出符合条件的网络。为了增添几分趣味与竞技性，大家甚至就此展开了一场小小的比赛，看谁能构造出总关注数最少的社交网络。

在这一社交平台上，共有 $n$ 位用户。小 S 收集到了一个大小为 $m$ 的数字集合 $\{c_1, \dots, c_m\}$。根据这些信息，一个可能的关注网络可以抽象为一张满足以下条件的有向图 $G = (V, E)$： - 包含 $n$ 位用户，即顶点集合 $V = \{1, 2, \dots, n\}$； - 不存在自己关注自己或重复关注的情况，即图 $G$ 不含自环与重边； - 所有关注关系均为严格的**单向关注**，即对于任意有向边 $(u, v) \in E$，均满足 $(v, u) \notin E$； - 对于集合中的每一个元素 $c_i \ (1 \le i \le m)$，图 $G$ 中都至少存在一个顶点，其出度（对应关注数）或入度（对应粉丝数）恰好等于 $c_i$。 你需要根据小 S 收集到的信息，还原出一个总关注数最少（即图 $G$ 边数最小）的关注网络。

输入的第一行包含一个非负整数 $o \in \{0, 1\}$，表示输出的参数。 输入的第二行包含两个正整数 $n, m \ (1 \le m < n \le 10 ^ 6)$，表示用户数量与小 S 收集到的集合的大小。保证若 $o = 0$，则 $n \le 2 \times 10 ^ 3$。 输入的第三行包含 $m$ 个两两不同的正整数 $c_1, c_2, \dots, c_m \ (1 \le c_i \le n - 1)$，表示小 S 收集到的集合中的元素。

输出一行一个正整数 $k$，表示所有可能的关注网络中总关注数的最小值。 若 $o = 0$，则接下来输出 $k$ 行，每行包含两个正整数 $u, v \ (1 \le u, v \le n)$，表示用户 $u$ 关注了用户 $v$，即 $(u, v) \in E$。

对于样例，图 $G$ 一共有 $7$ 条边，其中顶点 $4$ 的出度是 $3$，顶点 $2$ 的入度是 $1$，顶点 $3$ 的出度是 $4$，顶点 $1$ 的入度是 $2$。可以证明 $7$ 是图 $G$ 的最少边数。