CF245G Suggested Friends

Polycarpus 在一家初创社交网络担任程序员。他的老板给了他一个任务，要开发一个用于确定推荐好友的机制。Polycarpus 思考了很久这个问题，得出了如下结论。 设社交网络中的所有好友关系由 $m$ 对用户名 $a_i, b_i$（$a_i \ne b_i$）描述。每对 $a_i, b_i$ 表示用户 $a_i$ 和 $b_i$ 是好友。好友关系具有对称性，即如果 $a_i$ 与 $b_i$ 是好友，则 $b_i$ 也与 $a_i$ 是好友。对于用户 $x$，如果用户 $y$ 满足以下条件，则称用户 $y$ 是 $x$ 的推荐好友： 1. $x \ne y$； 2. $x$ 和 $y$ 不是好友； 3. 在所有同时符合前两条的网络用户中，$y$ 和 $x$ 有最多的共同好友。若 $z$ 同时是 $x$ 的好友且是 $y$ 的好友，$z \ne x, z \ne y$，则 $z$ 称为 $x$ 和 $y$ 的共同好友。 你的任务是帮助 Polycarpus 实现一个确定推荐好友机制。

第一行包含一个整数 $m$ $(1 \leq m \leq 5000)$——社交网络中好友对的数量。接下来的 $m$ 行，每行包含一对互为好友的用户名。第 $i$ 行包含用空格隔开的 $a_i$ 和 $b_i$ （$a_i \ne b_i$）。用户名非空，由不超过 20 个英文字母（大小写）组成。 保证每对好友在输入中只出现一次。例如，输入中不会同时出现 $x, y$ 和 $y, x$。保证不同用户的用户名互不相同。保证每个社交网络用户至少有一个好友。这保证每个用户名至少在输入中出现一次。

第一行输出一个整数 $n$，表示社交网络中用户的数量。接下来的 $n$ 行，每行输出一个用户的用户名 $c_i$ 和他的推荐好友个数 $d_i$，中间以空格分隔。 你可以以任意顺序输出用户信息。

在第一个测试样例中，考虑用户 David。用户 Mike 和 Tank 与 David 都有一个共同好友（Gerald）。用户 Kate 与 David 没有共同好友。因此，David 的推荐好友是 Mike 和 Tank。 由 ChatGPT 5 翻译