蒙蒙与希蒙的树上博弈

题目背景

上次是蒙蒙带着希蒙玩游戏，这次换成了希蒙带蒙蒙玩游戏！

题目描述

给定一棵$n$个节点的树，蒙蒙最初站在$x$节点上，希蒙站在$y$节点上。

他们轮流操作移动，且蒙蒙先移动。在每次移动中，假设当前在$i$号点，则其可以选择一个相邻节点$j$并且移动到$j$，请注意，他们不允许移动到一个当前任意玩家已经经过过的点上。

若他们其中之一无法移动，则其输了。

请你判断一下蒙蒙是否能够获得胜利。

输入格式

请注意输入文件名。

本题有多组数据。

第一行一个整数$t$，表示组数。

接下来每一组数据都按如下格式给出。

第一行三个整数$n,x,y$，含义见上。

接下来共$n-1$行，每行两个整数$u,v$，即树上的一条$u$到$v$的边。

输出格式

请注意输出文件名。

你一共需要输出一个整数$1$或$0$，$1$表示蒙蒙获胜，$0$表示希蒙获胜。

样例 #1

样例输入 #1

3
5 2 3
2 5
5 4
5 1
3 4
5 3 5
2 4
1 5
4 3
1 4
5 1 2
3 4
4 2
5 1
4 5

样例输出 #1

1
1
0

样例 #2

样例输入 #2

我们提供了两组额外的数据，其中第二组数据是为链的数据，请参考tree文件夹。

样例输出 #2

我们提供了两组额外的数据，其中第二组数据是为链的数据，请参考tree文件夹。

提示

数据范围：

对于30%的数据，我们保证$1<=n<=10^3,1<=t<=5$。

对于另外的20%的数据，我们保证图为一条链。

对于100%的数据，我们保证$1<=t<=500,1<=n<=10^5,1<=x,y<=n,x\not=y$。

我们保证，$\sum n <= 6\times10^5$。