题目描述

某个国家有若干个机场，某些机场之间有航班相连。乘客可以从任意一个机场飞往另一个机场（可能需要中转）。并且，任意两个机场之间仅存在唯一的飞行路线。

两名恐怖分子在玩一个游戏，他们轮流进行操作。每次操作包含以下步骤： 玩家选择一个机场放置炸弹，并选择一条航班与同伙一起飞离。 起飞后引爆炸弹，导致刚离开的机场被摧毁，所有与该机场相连的航班均无法使用。 飞机降落后，轮到另一名玩家操作，依此类推。 无法进行操作的一方输掉游戏。

给定初始航班列表以及游戏开始时恐怖分子所在的机场编号 $K$，请编写程序判断在双方均采取最优策略的情况下谁会获胜。

输入格式

• 第一行包含两个整数 $N$ 和 $K$，分别表示机场数量（$N \leq 1000$）和起始机场编号（$1 \leq K \leq 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 2000