拉登有一天遇见了萨达姆。正好两个人都有空，于是他们决定玩一个游戏。
他们有一张美国航线图，其中有N个机场和N-1条航线，所有机场可以互达（直接或者转机）。
一开始他们潜入美国某一个机场，两个人一起坐飞机旅游。
两个人轮流决定下一步的目的地机场，他们飞离某个美国机场后就会把那个机场炸掉。
如果轮到谁时不能走了（所有和他所在机场有航线的机场都被炸掉了），他就算输了。
给定机场和航线还有他们开始所在的机场，问谁会赢得游戏。假设两个人都用最优策略。
input：
第1行两个整数N和K。N为机场数(N<=1000)，K是他们一开始所在机场的编号(1 <= K<= N)。
接下来n-1行每行两个整数，表示一条航线连接的两个机场。每个机场最多连20条航线。
output：
如果先走的那个人赢，输出 "First player wins flying to airport L"，
L是先走的人第一次飞向的机场编号。如果有多个L输出最小的一个。
如果先走的人输，输出"First player loses"。
input：
4 3
3 2
3 1
1 4
output：
First player wins flying to airport 2
分析：
任何一对机场只有唯一线路，也就是说原图是一个树。两个恐怖分子都一起行动。以起点为根，设f[i]表示在机 场i行动的人的胜负，显然若i为叶子则f[i]=false。若i的任何一个儿子j有f[j]=false则f[i]=true。如此递推，一遍DFS搞定。
【参考程序】：
#include<iostream>
using namespace std;
int n,root,c,ans;
int pre[2010],now[1010],child[2010];
bool v[1010],f[1010];
void dfs(int k)
{
v[k]=false;
while (now[k])
{
if (v[child[now[k]]])
{
dfs(child[now[k]]);
if (f[child[now[k]]]==false)
{
f[k]=true;
if (k==root)
{
if (ans>child[now[k]])
ans=child[now[k]];
}
else return ;
}
}
now[k]=pre[now[k]];
}
}
int main()
{
scanf("%d%d",&n,&root);
memset(now,0,sizeof(now));
c=0; int a,b;
for (int i=1;i<=n-1;i++)
{
scanf("%d%d",&a,&b);
c++;child[c]=a;pre[c]=now[b];now[b]=c;
c++;child[c]=b;pre[c]=now[a];now[a]=c;
}
memset(v,true,sizeof(v));
memset(f,false,sizeof(f));
ans=n+2;
dfs(root);
if (!f[root]) printf("First player loses\n");
else printf("First player wins flying to airport %d\n",ans);
return 0;
}