CF1363C.Game On Leaves

Ayush and Ashish play a game on an unrooted tree consisting of $n$ nodes numbered $1$ to $n$. Players make the following move in turns:

• Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to $1$.

A tree is a connected undirected graph without cycles.

There is a special node numbered $x$. The player who removes this node wins the game.

Ayush moves first. Determine the winner of the game if each player plays optimally.

Ayush 和 Ashish 在一棵包含 $n$ 个节点（编号为 $1$ 到 $n$）的无根树上进行一场游戏。双方轮流执行以下操作：

• 选择树中的任意一个叶节点，并将其连同任意一条以该节点为端点的边一并移除。叶节点是指度数小于等于 $1$ 的节点。

树是一种无环的连通无向图。

其中存在一个特殊节点，编号为 $x$。移除该节点的玩家获胜。

Ayush 先手。若双方均采取最优策略，请判断游戏的获胜者。

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10)$ — the number of testcases. The description of the test cases follows.

The first line of each testcase contains two integers $n$ and $x$ $(1\leq n \leq 1000, 1 \leq x \leq n)$ — the number of nodes in the tree and the special node respectively.

Each of the next $n-1$ lines contain two integers $u$, $v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$, meaning that there is an edge between nodes $u$ and $v$ in the tree.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$）——表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1\leq n \leq 1000$，$1 \leq x \leq n$）——分别表示树中节点的数量以及特殊节点的编号。

接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，且 $u \ne v$），表示树中节点 $u$ 与节点 $v$ 之间存在一条边。

For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).

对于每个测试用例，如果 Ayush 获胜，则输出 “Ayush”，否则输出 “Ashish”（不带引号）。

For the $1$st test case, Ayush can only remove node $2$ or $3$, after which node $1$ becomes a leaf node and Ashish can remove it in his turn.

For the $2$nd test case, Ayush can remove node $2$ in the first move itself.

对于第 $1$ 个测试用例，Ayush 只能移除节点 $2$ 或 $3$，之后节点 $1$ 将变为叶节点，Ashish 可在自己的回合中将其移除。

对于第 $2$ 个测试用例，Ayush 在第一步即可移除节点 $2$。