Лісоруб#4808
Двоє гравців грають у таку гру: є дерево з визначеною кореневою вершиною. Гравці по черзі роблять ходи. На кожному ході гравець відрізає гілку (видаляє ребро), і з двох утворених зв'язаних компонент залишається лише та, що містить корінь; інша компонента вилучається й більше не бере участі в грі. Програє той гравець, який не може зробити хід.
Визначте, чи може перший гравець виграти гру, і якщо так — наведіть будь-який його виграшний хід.
Перший рядок містить два цілих числа та — кількість вершин у дереві та номер кореневої вершини відповідно (1 < N \leq 100\,000, 1 \leq R \leq N). Кожен з наступних N - 1 рядків містить по два цілих числа, що описують ребро між двома вершинами.
Виведіть одне ціле число: або — номер гравця, який виграє за оптимальної гри. Якщо перший гравець може виграти, також виведіть будь-який його виграшний хід: індекс ребра у вхідних даних (від до N - 1), яке потрібно відрізати у першому ході.
Приклад 1