Иерархия Паучьего сообщества
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В «Паучьем сообществе» есть понятная иерархия того, кто кому подчиняется. Разумеется, это не означает, что кто-то из Людей-Пауков менее или более важен, чем другие, но во время проведения операций по спасению мультивселенной важно, чтобы кто-то отвечал за координацию участников операции.

Всего в сообществе $$$n$$$ Пауков, и его иерархия представляет собой подвешенное дерево. Корнь этого дерева — паук под номером $$$1$$$, Мигель О'Хара. Сама иерархия задается $$$n - 1$$$ связями непосредственного подчинения между членами сообщества. Будем говорить, что Паук номер $$$u$$$ — «ментор» Паука $$$v$$$, если между ними есть связь непосредственного подчинения, и $$$u$$$ располагается в иерархии ближе к Мигелю, чем $$$v$$$. В таком случае будем называть $$$v$$$ «подчиненным» $$$u$$$.

После появления Майлза в сообществе, и его побега, члены сообщества разделились на две группы, у каждой из которых свое понимание того, как им следует действовать дальше. Назовем эти два имеющихся мнения A и B. Беспорядком в сообществе назовем количество таких пар $$$u$$$ и $$$v$$$, что Паук номер $$$u$$$ — ментор Паука номер $$$v$$$ (а $$$v$$$, соответственно — подчиненный $$$u$$$), и при этом у Паука номер $$$u$$$ мнение A, а у паука номер $$$v$$$ мнение B.

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

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

В первой строке ввода дано единственное целое число $$$n$$$ — количество Людей-Пауков в «Паучьем сообществе» ($$$1 \le n \le 10^5$$$).

В следующих $$$n - 1$$$ строках дано по два целых числа $$$a_i$$$ и $$$b_i$$$, означающих, что между Пауками $$$a_i$$$ и $$$b_i$$$ есть связь непосредственного подчинения ($$$1 \le a_i, b_i \le n$$$). При этом не обязательно, что $$$a_i$$$ — ментор $$$b_i$$$, может быть и наоборот.

Гарантируется, что набор связей образует дерево.

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

В первой строке выведите через пробел два целых числа — максимальное возможное значение беспорядка $$$d$$$ в такой иерархии, и $$$k$$$ — количество Людей-Пауков, придерживающихся мнения A.

Во второй строке через пробел перечислите $$$k$$$ различных чисел от $$$1$$$ до $$$n$$$ — номера Пауков, придерживающихся мнения A.

Если существует несколько возможных ответов с максимальным значением $$$d$$$, выведите любой из них.

Примеры

Входные данные
3
1 2
2 3
Выходные данные
1 1
2 
Входные данные
4
1 2
1 3
1 4
Выходные данные
3 1
1 
Входные данные
8
1 2
1 3
2 8
3 4
3 5
3 6
5 7
Выходные данные
4 2
2 3