eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Лісоруб

Лісоруб

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Двоє грають у наступну гру: є дерево з відміченою вершиною (коренем). Гравці ходять по черзі. За один хід гравець розрубує гілку (витирає ребро), причому з двох отриманихя компонент зв'язності залишається лише та, яка містить корінь - інша відвалюється і більше у грі не приймає участь. Прогає той, хто не може зробити хід.

Визначіть, чи може виграти перший гравець, і якщо да. то вкажіть довільний з його вииграшних ходів.

Вхідні дані

У першому рядку вхідного файлу знаходиться 2 числа N та R - кількість вершин дерева та номер кореня (1 < N100000, 1RN). Далі йде N-1 рядків, у кожному з яких знаходиться два числа - номери вершин, які з'єднує чергове ребро.

Вихідні дані

Виведіть у вихідний файл одне число: 1 або 2 - номер гравця, який виграє при правильній грі. Якщо виграє перший гравець, то виведіть також довільний його виграшний хід, тобто порядковий номер ребра у вхідному файлі, яке йому достатньо розрубати першим ходом (число від 1 до N-1).

Приклад

Вхідні дані #1
5 5
2 3
1 3
2 5
4 5
Вихідні дані #1
1
1