P14500 [NCPC 2025] Follower Forensics

你的社交媒体公司 ConnectHub 以其网络中信息传播的高效便捷而自豪。 :::align{center}  ::: 用户可以通过分享按钮直接将帖子分享给自己的关注者，也可以通过在评论区发帖把内容传递给自己所关注的账号。ConnectHub 因其用户的强大传播力而闻名：任意账号发布的帖子，都能够通过一系列分享或评论传播到任何其他账号。 但灾难发生了：一次数据库事故清除了所有 “谁关注了谁” 的记录。不过似乎仍有部分数据幸存——对每个账号来说，你仍然知道它关注了多少账号，以及它有多少关注者。当然，这些数字也有可能已被破坏，但这是你仅剩的全部信息。 你的任务是重建丢失的关注关系数据库，使得每个账号的关注数与被关注数都与给定的数据一致，并且保证 ConnectHub 再次实现完全的可传播性。

输入包含： - 一行，一个整数 $n$，表示账号数量，满足 $1 \le n \le 100\,000$； - 一行，包含 $n$ 个整数 $a_1, \ldots, a_n$，满足对每个 $i$ 均有 $0 \le a_i \le n$，其中 $a_i$ 表示第 $i$ 个账号关注的账号数； - 一行，包含 $n$ 个整数 $b_1, \ldots, b_n$，满足对每个 $i$ 均有 $0 \le b_i \le n$，其中 $b_i$ 表示第 $i$ 个账号的关注者数量。 此外，保证： $$ \sum_{i=1}^n a_i \;+\; \sum_{i=1}^n b_i \;\le\; 2\,000\,000. $$ 需要注意的是，输入数据并不保证一定存在可重建的网络，不管该网络是否满足完全传播性。对熟悉相关术语的人来说，“完全传播性”等价于弱连通性。

如果存在可行重建方案，则输出一个网络： - 第一行输出两个整数：账号数量 $n$ 与连接数量 $m$（即关注关系数量），这里的 $n$ 与输入一致； - 接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示账号 $a$ 关注账号 $b$。 否则输出 `impossible`。 注意：一个账号不能关注同一个账号两次，也不能关注自己。

翻译由 ChatGPT-5 完成