P16533 [THUPC 2026 Final] Social Network

From the THU Student Programming Contest and Collegiate Invitational (THUPC2026) Final in 2026. Editorials and other resources can be found at https://github.com/dapingguo8/THUPC2026-final. > After discussing the headache-inducing research and paper reviewing, the topic of the tea party gradually shifted to daily social life. Little T excitedly shared an interesting discovery: on a commonly used social platform, the follow relationships between users are all strictly **one-way follows**, meaning there is no pair of users who follow each other. > > This curious phenomenon immediately sparked discussion. Little S then extracted some statistics of the network and collected each user’s following count and follower count. Unfortunately, during the circulation of the data, she accidentally lost part of it, and in the end only a set of several positive integers remained. Little S found that for every element in the set, one can always find at least one user whose following count or follower count is exactly that element. > > Since the platform keeps the complete follow structure confidential, the exact social graph can no longer be known. To verify whether the remaining data is reasonable, everyone picked up paper and pen and tried to reconstruct a network that meets the conditions. To make it more fun and competitive, they even held a small contest to see who could construct a social network with the minimum total number of follows.

On this social platform, there are $n$ users. Little S collected a set of numbers of size $m$, $\{c_1, \dots, c_m\}$. Based on this information, a possible follow network can be modeled as a directed graph $G = (V, E)$ that satisfies: - It contains $n$ users, i.e. the vertex set is $V = \{1, 2, \dots, n\}$. - No user follows themselves and there are no duplicate follows, i.e. $G$ has no self-loops or multiple edges. - All follow relationships are strictly **one-way follows**, i.e. for any directed edge $(u, v) \in E$, it holds that $(v, u) \notin E$. - For every element $c_i \ (1 \le i \le m)$ in the set, there exists at least one vertex in $G$ whose out-degree (following count) or in-degree (follower count) is exactly $c_i$. You need to reconstruct a follow network with the minimum total number of follows (i.e. the minimum number of edges in $G$) according to the information collected by Little S.

The first line contains a non-negative integer $o \in \{0, 1\}$, indicating the output mode. The second line contains two positive integers $n, m \ (1 \le m < n \le 10 ^ 6)$, representing the number of users and the size of the set collected by Little S. It is guaranteed that if $o = 0$, then $n \le 2 \times 10 ^ 3$. The third line contains $m$ pairwise distinct positive integers $c_1, c_2, \dots, c_m \ (1 \le c_i \le n - 1)$, representing the elements in the set collected by Little S.

Output one line with a positive integer $k$, representing the minimum possible total number of follows among all valid networks. If $o = 0$, then output $k$ more lines, each containing two positive integers $u, v \ (1 \le u, v \le n)$, meaning that user $u$ follows user $v$, i.e. $(u, v) \in E$.

For the sample, the graph $G$ has a total of $7$ edges. Vertex $4$ has out-degree $3$, vertex $2$ has in-degree $1$, vertex $3$ has out-degree $4$, and vertex $1$ has in-degree $2$. It can be proven that $7$ is the minimum number of edges in $G$. Translated by ChatGPT 5