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。