Поликарп работает программистом в одной развивающейся социальной сети. Начальство поставило перед ним задачу разработать механизм определения возможных друзей. Поликарп долго думал над поставленной задачей и пришел к следующему выводу.
Пусть заданы все отношения дружбы в социальной сети в виде m пар имен пользователей ai, bi (ai ≠ bi). Каждая пара ai, bi обозначает, что пользователи ai и bi являются друзьями. Отношение дружбы симметричное, то есть если ai друг bi, то и bi друг ai. Пользователь y является возможным другом пользователя x, если выполняются условия:
Ваша задача, помочь Поликарпу реализовать механизм определения возможных друзей.
В первой строке записано единственное целое число m (1 ≤ m ≤ 5000) — количество пар друзей в социальной сети. В следующих m строках заданы пары имен пользователей-друзей. В i-той строке через пробел записаны два имени ai и bi (ai ≠ bi). Имена пользователей непустые и состоят из не более 20 заглавных и строчных латинских букв.
Гарантируется, что каждая пара друзей встречается во входных данных только один раз, например, во входных данных одновременно не могут встречаться пары x, y и y, x. Гарантируется, что различные пользователи имеют различные имена. Гарантируется, что каждый пользователь социальной сети имеет хотя бы одного друга. Последнее гарантирует, что имя каждого пользователя социальной сети встречается во входных данных хотя бы один раз.
В первой строке выведите единственное целое число n — количество пользователей социальной сети. В следующих n строках выведите для каждого пользователя, количество возможных друзей. В i-той строке выведите имя пользователя ci и количество его возможных друзей di через пробел.
Информацию про пользователей можно выводить в любом порядке.
В первом тестовом примере рассмотрим пользователя David. Пользователи Mike и Tank имеют одного общего друга (Gerald) с David. Пользователь Kate не имеет ни одного общего друга с David. Поэтому возможные друзья David: пользователи Mike и Tank.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач