H. HEX-A-GONE Trails

Problem Description

Consider a tree of $n$ nodes. Two OPs, OP I and OP II are playing a game on the tree. In the beginning, OP I and OP II are at node $x$ and node $y$, respectively. Then they take turns to move, OP I moves first. In each move, a player at node $i$ must choose a neighboring node $j$ and move to $j$. Remind that a player is not allowed to move to the other player's current position. After this move, node $i$ becomes invalid, meaning it cannot be moved to in the following moves of both players. If a player cannot make a valid move, he will lose the game. Please determine whether OP I has a strategy to make sure he will win.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 500$) - the number of test cases. Description of the test cases follows. The first line of each test case contains one integer $n$ ($1\leq n\leq 10^5$). The second line contains two integers $x,y$ ($1\leq x,y\leq n$, $x\neq y$). Each of the following $n - 1$ lines contains two integers $u,v$ ($1\leq u,v\leq n$, $u\neq v$) - an edge between $u,v$. It's guaranteed that $\sum n\leq 6\times 10^5$.

Output

For each test case, print a single integer - If OP I has a strategy to make sure he will win, output $1$. Otherwise output $0$.

Sample Input

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

Sample Output

1
1
0

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）