О-о-о, подосиновичек
О-о-о, рыжик...
В лесу неподалёку растёт очень много грибов и находится ещё большее количество опушечек. Для удобства ориентации в лесу грибники пронумеровали опушечки леса номерами от 1 до $$$n$$$. Также известно, что вход в лес находится на опушечке под номером $$$s$$$.
Грибники протоптали в лесу целую сеть тропинок. Любая тропинка соединяет между собой две опушечки в лесу. На каждой опушечке либо растёт ровно один гриб, либо не растёт ничего. Чтобы не теряться в лесу, грибники проложили лишь самые необходимые тропинки, поэтому между любыми двумя опушечками в лесу существует только одна связывающая их последовательность тропинок, в которой тропинки не повторяются. Кроме того, известно, что грибы растут на тех и только тех опушечках, которые не являются промежуточными ни на одном пути от входа в лес до другой опушечки.
Вы хотите сходить в лес и собрать в нём как можно больше грибов. Начиная от входа в лес, вы можете ходить по всем тропинкам сколько угодно раз. Однако, если вы не хотите заблудиться, то лучше запомнить самую первую тропинку, по которой вы прошли, и не ходить по ней больше одного раза. Какое максимальное количество грибов вы можете собрать?
В первой строке входного файла записаны два целых числа $$$n$$$ и $$$s$$$ — количество опушечек и номер опушечки, на которой расположен вход в лес соответственно ($$$6 \leq n \leq 10^5$$$, $$$1 \leq s \leq n$$$).
В каждой из следующих $$$n - 1$$$ строк записано по два числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — это номера опушечек, являющихся концами $$$i$$$-й тропинки.
В единственной строке ваша программа должна вывести два целых числа. Первое число — это максимально возможное количество грибов, которое можно собрать. Второе число — это номер первой опушечки, на которую нужно пойти, чтобы собрать как можно больше грибов при условии, что вы не будете больше одного раза ходить по самой первой тропинке, по которой вы прошли. Если таких опушечек несколько, выведите любую из них.
В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.
| Подзадача | Баллы | Дополнительные | Необходимые | Система |
| ограничения | подзадачи | оценки | ||
| $$$0$$$ | $$$0$$$ | Тесты из условия | — | — |
| $$$1$$$ | $$$10$$$ | $$$n \le 100$$$ | $$$0$$$ | полная |
| $$$2$$$ | $$$40$$$ | $$$n \le 1000$$$ | $$$0$$$, $$$1$$$ | полная |
| $$$3$$$ | $$$50$$$ | — | $$$0$$$, $$$1$$$, $$$2$$$ | полная |
6 34 35 63 21 53 5
2 5
