Alice and Bob play a game by taking turns moving a token in a tree. Alice goes first. On their turn, the player moves the token from its current vertex $$$a$$$ to a vertex $$$b$$$. The length of the move is the number of edges on the unique simple path from $$$a$$$ to $$$b$$$. Each move must be strictly longer than the previous move, and Alice's first move must have positive length.
A player who has no legal move on their turn loses, and the other player wins. Given the tree and initial position of the token, determine who will win the game if both players play optimally.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n \leq 2\cdot10^5$$$) — the number of vertices in the tree and the initial position of the token.
The next $$$n - 1$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\leq u_i,\,v_i\leq n$$$) — the $$$i$$$-th edge in the tree.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output Alice if Alice wins with optimal play, or Bob if Bob wins.
31 16 11 21 31 44 54 615 81 22 32 41 55 65 71 88 99 109 1111 128 1313 1414 15
BobAliceBob
In the first test case, Alice has no move since there are no nodes with a nonzero distance away from the token.
In the second test case, which is shown in the statement, Alice can move the token a distance of $$$1$$$ to node $$$4$$$. This leaves nodes $$$2$$$ and $$$3$$$ as Bob's only moves. In either case, she can respond with a move to node $$$5$$$ and win.
In the third test case, it can be shown that Bob has a winning strategy.
