G. Возможные друзья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Поликарп работает программистом в одной развивающейся социальной сети. Начальство поставило перед ним задачу разработать механизм определения возможных друзей. Поликарп долго думал над поставленной задачей и пришел к следующему выводу.

Пусть заданы все отношения дружбы в социальной сети в виде m пар имен пользователей ai, bi (ai ≠ bi). Каждая пара ai, bi обозначает, что пользователи ai и bi являются друзьями. Отношение дружбы симметричное, то есть если ai друг bi, то и bi друг ai. Пользователь y является возможным другом пользователя x, если выполняются условия:

  1. x ≠ y;
  2. x и y не являются друзьями;
  3. среди всех пользователей социальной сети, которые удовлетворяют первым двум условиям, пользователь y имеет наибольшее количество общих друзей с пользователем x. Пользователь z является общим другом пользователя x и пользователя y (z ≠ x, z ≠ y), если x и z друзья, а также y и z друзья.

Ваша задача, помочь Поликарпу реализовать механизм определения возможных друзей.

Входные данные

В первой строке записано единственное целое число m (1 ≤ m ≤ 5000) — количество пар друзей в социальной сети. В следующих m строках заданы пары имен пользователей-друзей. В i-той строке через пробел записаны два имени ai и bi (ai ≠ bi). Имена пользователей непустые и состоят из не более 20 заглавных и строчных латинских букв.

Гарантируется, что каждая пара друзей встречается во входных данных только один раз, например, во входных данных одновременно не могут встречаться пары x, y и y, x. Гарантируется, что различные пользователи имеют различные имена. Гарантируется, что каждый пользователь социальной сети имеет хотя бы одного друга. Последнее гарантирует, что имя каждого пользователя социальной сети встречается во входных данных хотя бы один раз.

Выходные данные

В первой строке выведите единственное целое число n — количество пользователей социальной сети. В следующих n строках выведите для каждого пользователя, количество возможных друзей. В i-той строке выведите имя пользователя ci и количество его возможных друзей di через пробел.

Информацию про пользователей можно выводить в любом порядке.

Примеры
Входные данные
5
Mike Gerald
Kate Mike
Kate Tank
Gerald Tank
Gerald David
Выходные данные
5
Mike 1
Gerald 1
Kate 1
Tank 1
David 2
Входные данные
4
valera vanya
valera edik
pasha valera
igor valera
Выходные данные
5
valera 0
vanya 3
edik 3
pasha 3
igor 3
Примечание

В первом тестовом примере рассмотрим пользователя David. Пользователи Mike и Tank имеют одного общего друга (Gerald) с David. Пользователь Kate не имеет ни одного общего друга с David. Поэтому возможные друзья David: пользователи Mike и Tank.