U381984 【搬运】我推的博弈

我推的卡空间模拟赛

考虑一个包含 $n$ 个节点的树。在这棵树上，我推的孩子星野阿库亚（阿库亚）和星野露比（露比），正在进行一场游戏。一开始，阿库亚位于节点 $x$，露比位于节点 $y$。然后，他们轮流移动，阿库亚先开始。每一轮中，位于节点 $i$ 的角色必须选择一个相邻节点 $j$ 并移动到 $j$。需要注意的是，角色不能移动到另一位角色当前的位置。在完成这个移动后，节点 $i$ 将变为无效，意味着在接下来的回合中，两位角色都不能移动到该节点。 如果某位角色无法进行有效的移动，他或她将输掉游戏。 请确定星野阿库亚是否有策略可以确保她赢得游戏。

输入包含多个测试用例。 第一行包含一个整数 $T$ 表示测试用例的数量。 接下来是各个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$。 第二行包含两个整数 $x$ 和 $y$。 接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 之间存在一条边。

对于每个测试用例，输出一个整数： 如果星野阿库亚有策略可以确保她赢得游戏，则输出 $1$，否则输出 $0$。

$T\leq 500$，$n\leq 10^5$，$\sum n\leq 5\times 10^5$。