Забавна гра
У одній країні є декілька аеропортів, між деякими аеропортами є рейси. Можна перелетіти з довільного аеропорту у довільний інший, можливо, з декількома пересадками. Для кожної пари аеропортів існує лише одна послідовність рейсів, які з'єднують ці аеропорти.
Два терористи грають у гру. Вони роблять ходи по черзі. Кожен хід полягає у наступних діях. Гравець мінує аеропорт, вибирає рейс і вилітає разом зі своїм колегою. Після зльоту він активує радіокерований детонатор. У результаті аеропорт, який тільки що залишили терористиы, зрйновано, і рейси у цей аеропорт та з нього більше неможливі. Після того, як літак приземлюється, інший гравець робить хід — і далі по черзі. Програє той, хто не може зробити хід.
Напишіть програму, яка за початковим списком польотів та номером аеропорту, у якому терористи починають гру, визначає, хто виграє, якщо терористи грають ідеально (кожен обирає кращий хід).
Вхідні дані
Перший рядок містить два цілих числа: n та k, відокремлені пропуском. Туть n — кількість аеропортів (n ≤ 1000), а k — номер аеропорту, який є початковою точкою гри (1 ≤ k ≤ n). Наступні n−1 рядків містять пари цілих чисел, відокремлених пропусками. Це номери аеропортів, з'єднаних рейсом. Усі рейси двосторонні і згадані лише один раз. Кожен аеропорт з'єднано рейсами не більше, ніж з 20 іншими.
Вихідні дані
Якщо гравець, який розпочинає гру, виграє, програма повинна написати "First player wins flying to airport L", де L — номер аеропорту, у який гравець повинен вилетіти з поточного. Якщо таких аеропортів декілька, програма повинна вибрати варіант з меншим номером аеропорту. Якщо гравець, що починє, програє, програма повинна написати "First player loses".