ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1045. Забавная игра

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в любой другой, возможно, с несколькими пересадками. Для каждой пары аэропортов существует только одна последовательность рейсов, соединяющая эти аэропорты.
Два террориста играют в игру. Они делают ходы по очереди. Каждый ход заключается в следующих действиях. Игрок минирует аэропорт, выбирает рейс и улетает вместе со своим коллегой. После взлёта он активирует радиоуправляемый взрыватель. В результате аэропорт, который только что покинули террористы, разрушен, и рейсы в этот аэропорт и из него больше невозможны. После того, как самолёт приземляется, другой игрок делает ход — и дальше по очереди. Проигрывает тот, кто не может сделать ход.
Напишите программу, которая по начальному списку полётов и номеру аэропорта, в котором террористы начинают игру, определяет, кто выигрывает, если террористы играют идеально (каждый выбирает лучший ход).

Исходные данные

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n ≤ 1000), а k — номер аэропорта, являющегося начальной точкой игры (1 ≤ k ≤ n). Следующая n − 1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

Результат

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L», где L — номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses».

Пример

исходные данныерезультат
4 3
3 2
3 1
1 4
First player wins flying to airport 2
Автор задачи: Дмитрий Филимоненков
Источник задачи: Ural State University collegiate programming contest (25.03.2000)