← 返回题目列表

Codeforces · 245/G

G. 推荐的朋友

中文机器翻译题面 查看原题

Polycarpus 在一家初创社交网络中担任程序员。他的老板给了他一项任务,要求他开发一种确定推荐朋友的机制。波利卡波斯对这项任务进行了深思熟虑,并得出了以下结论。

假设社交网络中的所有友谊关系都以 m 个用户名对 ai, bi (ai ≠ bi) 的形式给出。每对 ai、bi 表示用户 ai 和 bi 是朋友。友谊是对称的,即如果ai是bi的朋友,那么bi也是ai的朋友。如果满足以下条件,则用户y是用户x的推荐好友:

1. x ≠ y;
2. x 和 y 不是朋友;
3、在满足前两个条件的所有网络用户中,用户y与用户x拥有最多的共同好友。如果x和z是朋友,并且y和z也是朋友,则用户z是用户x和用户y的共同朋友(z ≠ x, z ≠ y)。

你的任务是帮助 Polycarpus 实施一种确定推荐好友的机制。

输入

第一行包含一个整数 m (1 ≤ m ≤ 5000) — 社交网络中好友的数量。接下来的 m 行包含彼此为朋友的用户的姓名对。第 i 行包含两个空格分隔的名称 ai 和 bi (ai ≠ bi)。用户名不能为空,且最多由20个大小写英文字母组成。

保证每对朋友在输入中只出现一次。例如,输入不能同时包含x,y和y,x。保证不同的用户具有不同的名称。保证每个社交网络用户至少有一个朋友。最后一件事保证每个用户名在输入中至少出现一次。

输出

在第一行打印一个整数 n — 网络用户的数量。在接下来的 n 行中,打印每个用户建议的朋友数量。在第 i 行中,在空格后打印用户 ci 的名称和他推荐的好友数量 di 。

您可以按任意顺序打印有关用户的信息。

示例

输入 #1

5
Mike Gerald
Kate Mike
Kate Tank
Gerald Tank
Gerald David

输出 #1

5
Mike 1
Gerald 1
Kate 1
Tank 1
David 2

输入 #2

4
valera vanya
valera edik
pasha valera
igor valera

输出 #2

5
valera 0
vanya 3
edik 3
pasha 3
igor 3

注意

在第一个测试用例中,考虑用户 David。用户 Mike 和 Tank 与 David 有一个共同的朋友(杰拉德)。用户凯特和大卫没有共同的朋友。这就是为什么 David 建议的朋友是用户 Mike 和 Tank。