Suggested Friends

题意翻译

## 题目背景 Polycarpus 在一家初创的社交网络中担任程序员。他的老板给他的任务是开发一个推荐好友的程序。Polycarpus 对这个任务进行了很多思考，并得出了以下结论。 ## 题目描述 假设社交网络中的所有友情关系都可以用 $m$ 个用户名对 $a_{i}\ b_{i}(a_{i}\neq b_{i})$ 来描述。每一对 $a_{i}\ b_{i}$ 意味着用户 $a_{i}$ 和 $b_{i}$ 是朋友。友谊关系是满足交换律的，即如果 $a_{i}$ 是 $b_{i}$ 是朋友，那么 $b_{i}$ 也是 $a_{i}$ 的朋友，如果满足以下条件，用户 $y$ 是用户 $x$ 的推荐朋友: 1. $x\neq y$ 2. $y$ 不是 $x$ 的朋友 3. 在所有满足前两个条件的网络用户中，用户 $y$ 与用户 $x$ 的共同好友最多。如果 $x$ 和 $z$ 是朋友，且 $y$ 和 $z$ 也是朋友，则用户 $z$ 是用户 $x$ 和用户 $y$ 的共同好友 $(y\neq z,x\neq z)$。 你的任务是帮助 Polycarpus 实现一个确定推荐好友的程序。 ## 输入内容 第一行包含一个整数 $m(1\leq m\leq 5000)$ (社交网络中好友的对数)。接下来的 $m$ 行包含彼此为好友的用户名字对。第 $i+1$ 行包含两个空格分隔的名字 $a_{i}$ 和 $b_{i}(a_{i}\neq b_{i})$。用户的名字非空，最多包含20个英文大写或小写字母。 对于输入的数据，保证： - 每一对朋友在输入中只出现一次。例如，输入中不能同时包含 $x\ y$ 和 $y\ x$。 - 用户不重名。 - 每个社交网络用户至少有一个朋友。 - 每个用户名在输入中至少出现一次。 ## 输出结果 在第一行打印一个整数 $n$ - 网络用户的数量。在接下来的 $n$ 行中，打印每个用户的推荐好友数量。在第 $i+1$ 行中打印用户的名字 $c_{i}$ 和他推荐朋友的数量 $d_{i}$（两个数据相隔一个空格）。 你可以按任何顺序打印用户的信息。 ## 样例说明 在第一个样例中，考虑 David。用户 Mike 和 Tank 与 David 有一个共同的朋友（Gerald）。用户 Kate 与 David 没有共同的朋友。故 David 的推荐朋友是 Mike 和 Tank，即输出 2。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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.