Поликарп работает программистом в одной развивающейся социальной сети. Начальство поставило перед ним задачу разработать механизм определения возможных друзей. Поликарп долго думал над поставленной задачей и пришел к следующему выводу.
Пусть заданы все отношения дружбы в социальной сети в виде m пар имен пользователей ai, bi (ai ≠ bi). Каждая пара ai, bi обозначает, что пользователи ai и bi являются друзьями. Отношение дружбы симметричное, то есть если ai друг bi, то и bi друг ai. Пользователь y является возможным другом пользователя x, если выполняются условия:
- x ≠ y;
- x и y не являются друзьями;
- среди всех пользователей социальной сети, которые удовлетворяют первым двум условиям, пользователь y имеет наибольшее количество общих друзей с пользователем x. Пользователь z является общим другом пользователя x и пользователя y (z ≠ x, z ≠ y), если x и z друзья, а также y и z друзья.
Ваша задача, помочь Поликарпу реализовать механизм определения возможных друзей.
Выходные данные
В первой строке выведите единственное целое число n — количество пользователей социальной сети. В следующих n строках выведите для каждого пользователя, количество возможных друзей. В i-той строке выведите имя пользователя ci и количество его возможных друзей di через пробел.
Информацию про пользователей можно выводить в любом порядке.
Примечание
В первом тестовом примере рассмотрим пользователя David. Пользователи Mike и Tank имеют одного общего друга (Gerald) с David. Пользователь Kate не имеет ни одного общего друга с David. Поэтому возможные друзья David: пользователи Mike и Tank.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
Mike Gerald
Kate Mike
Kate Tank
Gerald Tank
Gerald David
|
5
Mike 1
Gerald 1
Kate 1
Tank 1
David 2
|
|
2
|
4
valera vanya
valera edik
pasha valera
igor valera
|
5
valera 0
vanya 3
edik 3
pasha 3
igor 3
|