Козак Вус у Деревляндії#10705
Нещодавно Козака Вуса обрали президентом Деревляндії, і перш за все він оцінив ситуацію з транспортом. У країні є міст, між якими вже прокладена мережа з n-1 дороги таким чином, що з будь-якого міста можна доїхати до будь-якого іншого, пересуваючись тільки вже збудованими дорогами.
Козак Вус вирішив провести транспортну реформу, в результаті якої послідовні дороги будуть об'єднані в траси. Для цього йому необхідно визначити одне з міст як столицю Деревляндії, після чого створити як можна менше трас таким чином, щоб зі столиці можна було добратись до будь-якого іншого міста, пересуваючись трасою. Трасою називається послідовність унікальних міст, що починається в столиці, і кожне з міст з'єднане зі своїми сусідами. Більш формально, це послідовність з міст a_1, a_2, \dots, a_k така, що a_1 є столицею, для будь-якого (1 \leq i < k) міста a_i та a_{i+1} зв'язані між собою дорогою, і всі елементи послідовності різні.
Козак Вус зараз зайнятий більш важливими справами, а тому просить вас допомогти йому обрати столицю таким чином, щоб необхідна кількість трас, яку потрібно створити, була мінімальною, а також порахувати цю кількість.
Зверніть увагу, що одна дорога може належати до декількох різних трас.
Перший рядок містить одне ціле число (2 \leq n \leq 2 \cdot 10^5) — кількість міст у Деревляндії.
Кожен з наступних n-1 рядків містить два цілих числа і (1 \leq u, v \leq n) — номери двох міст, між якими є дорога.
У першому рядку виведіть номер міста, яке Козак Вус зробить столицею. Якщо існує декілька відповідей, виведіть серед них найменшу.
У другому рядку виведіть кількість трас, яку потрібно створити так, щоб виконувалась необхідна умова.
Example 1
Example 2
У першому прикладі ми можемо обрати місто під номером як столицю і створити дві траси — (3, 2, 1, 4) та (3, 2, 1, 5).