ИТ-рестораны
ограничение по времени на тест: 4 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: standard input
вывод: standard output
В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n - 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.
Недавно мэр города придумал способ, устраняющий проблемы с общепитом и IT-инфраструктурой, причем одновременно! Решено поставить на перекрестках города ресторанчики двух известных сетей кафе для IT-шников: «iMac D0naldz» и «Burger Bing». Так как владельцы сетей не дружат, категорически запрещается размещать рестораны двух разных сетей на соседних перекрестках. Есть и другие требования. Вот полный список:
- в каждом перекрестке должен находится не более чем один ресторан;
- каждый ресторан принадлежит либо «iMac D0naldz», либо «Burger Bing»;
- каждая сеть должна построить не менее одного ресторана;
- не существует пары перекрестков, которые соединены дорогой и на которых стоят рестораны разных сетей.
Мэр собирается брать неплохой налог с каждого ресторана, поэтому он заинтересован в том, чтобы общее число ресторанов было максимальным.
Помогите мэру проанализировать ситуацию. Найдите все такие пары (a, b), что a ресторанов может принадлежать «iMac D0naldz», b — «Burger Bing», а сумма a + b максимальна.
Входные данные
В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n - 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi, yi (1 ≤ xi, yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.
Гарантируется, что заданная дорожная сеть представляет собой неориентированное дерево с n вершинами.
Выходные данные
В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a, b) в порядке увеличения первой компоненты a.
Примеры тестов
Входные данные
5
1 2
2 3
3 4
4 5
Выходные данные
3
1 3
2 2
3 1
Входные данные
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
Выходные данные
6
1 8
2 7
3 6
6 3
7 2
8 1
