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.

N/A

N/A

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.