Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сигизмунд Дийкстра управляет секретной службой королевства Редания. Его агенты собирают всю доступную информацию о Нильфгаардской империи, в том числе о запутанных взаимоотношениях между имперскими феодалами. Ведьмак в них совсем не разбирается, поэтому отвечать на вопросы Дийкстры придется вам.
Все известные феодалы пронумерованы от `1` до `N` включительно. Пока не поступила надежная информация, все они считаются независимыми друг от друга. Затем поступает `N-1` донесение вида «`A` стал вассалом `B`», означающее, что феодал `A` теперь подчиняется феодалу `B`. Каждый феодал может стать вассалом лишь единожды, после чего перейти в подчинение к другому феодалу либо стать независимым уже невозможно. В отношениях подчиненности нет циклов (то есть феодал не может подчиняться тому, кто подчиняется ему самому прямо или косвенно). Каждый феодал имеет свой ранг, определяющийся следующим образом: если у феодала нет подчиненных, то его ранг равен `1`, иначе ранг феодала на `1` больше максимального из рангов его непосредственных подчиненных.
Получив каждое из донесений, нужно определить `2` величины:
* номер феодала с максимальным рангом (во всей империи) и его ранг;
* номер феодала, имеющего максимальное количество подчиненных (прямых и косвенных, во всей империи), и это количество.
Если несколько феодалов имеют одинаковый максимальный ранг или одинаковое число подчиненных, нужно вывести максимальный из их номеров.
В первой строке входных данных указано единственное целое число `N` — количество феодалов в империи (`2 <= N <= 10^5`).
В каждой из следующих `N-1` строк указано по `2` различных числа `A, B` (`1 <= A, B <= N`) — донесения о том, что феодал `A` стал вассалом `B`. Гарантируется, что иерархия феодалов соответствует описанным выше правилам.
Выведите `N-1` строку, по `4` числа в каждой: максимальный из номеров самых высокоранговых феодалов и его ранг, максимальный из номеров феодалов с максимальным количеством подчиненных и это количество.
```sample Пример ввода
7
1 2
5 6
3 2
4 2
6 7
2 6
```
```sample Пример вывода
2 2 2 1
6 2 6 1
6 2 2 2
6 2 2 3
7 3 2 3
7 4 7 6
```
Начало
Рабочее место участника
Система непересекающихся множеств