CF245G.Suggested Friends

Polycarpus works as a programmer in a start-up social network. His boss gave his a task to develop a mechanism for determining suggested friends. Polycarpus thought much about the task and came to the folowing conclusion.

Let's say that all friendship relationships in a social network are given as m username pairs a__i, b__i (a__i ≠ b__i). Each pair a__i, b__i means that users a__i and b__i are friends. Friendship is symmetric, that is, if a__i is friends with b__i, then b__i is also friends with a__i. User y is a suggested friend for user x, if the following conditions are met:

1. x ≠ y;
2. x and y aren't friends;
3. among all network users who meet the first two conditions, user y has most of all common friends with user x. User z is a common friend of user x and user y (z ≠ x, z ≠ y), if x and z are friends, and y and z are also friends.

Your task is to help Polycarpus to implement a mechanism for determining suggested friends.

波利卡普斯是一家初创社交网络公司的程序员。他的老板交给他一项任务：开发一种推荐好友的机制。波利卡普斯对这项任务进行了深入思考，并得出了如下结论。

假设社交网络中的所有好友关系由 $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$ 的好友。用户 $y$ 是用户 $x$ 的推荐好友，当且仅当满足以下条件：

1. $x \ne y$；
2. $x$ 与 $y$ 不是好友；
3. 在所有满足前两个条件的网络用户中，用户 $y$ 与用户 $x$ 拥有最多数量的共同好友。用户 $z$（其中 $z \ne x$ 且 $z \ne y$）是用户 $x$ 与用户 $y$ 的共同好友，当且仅当 $x$ 与 $z$ 是好友，且 $y$ 与 $z$ 也是好友。

你的任务是帮助波利卡普斯实现这一推荐好友机制。

The first line contains a single integer m (1 ≤ m ≤ 5000) — the number of pairs of friends in the social network. Next m lines contain pairs of names of the users who are friends with each other. The i-th line contains two space-separated names a__i and b__i (a__i ≠ b__i). The users' names are non-empty and consist of at most 20 uppercase and lowercase English letters.

It is guaranteed that each pair of friends occurs only once in the input. For example, the input can't contain x, y and y, x at the same time. It is guaranteed that distinct users have distinct names. It is guaranteed that each social network user has at least one friend. The last thing guarantees that each username occurs at least once in the input.

第一行包含一个整数 $m$（$1 \le m \le 5000$），表示社交网络中朋友对的数量。
接下来的 $m$ 行每行包含一对互为朋友的用户姓名。第 $i$ 行包含两个以空格分隔的姓名 $a_i$ 和 $b_i$（$a_i \ne b_i$）。用户姓名非空，且仅由至多 20 个大小写英文字母组成。

保证输入中每对朋友仅出现一次。例如，输入中不会同时包含 $x, y$ 和 $y, x$。
保证不同用户的姓名互不相同。
保证每个社交网络用户至少有一个朋友。最后一条保证意味着每个用户名在输入中至少出现一次。

In the first line print a single integer n — the number of network users. In next n lines print the number of suggested friends for each user. In the i-th line print the name of the user c__i and the number of his suggested friends d__i after a space.

You can print information about the users in any order.

第一行输出一个整数 $n$ —— 网络用户的数量。接下来的 $n$ 行中，每行输出对应用户所推荐的好友数量。在第 $i$ 行中，先输出用户 $c_i$ 的姓名，然后输出其推荐好友数量 $d_i$，两者之间用一个空格分隔。

你可以以任意顺序输出各用户的信息。

In the first test case consider user David. Users Mike and Tank have one common friend (Gerald) with David. User Kate has no common friends with David. That's why David's suggested friends are users Mike and Tank.

在第一个测试用例中，考虑用户 David。用户 Mike 和 Tank 分别与 David 有 1 个共同好友（Gerald）。用户 Kate 与 David 没有共同好友。因此，David 的推荐好友是用户 Mike 和 Tank。