1363C. C. Game On Leaves

CF1363C. Game On Leaves

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

Ayush 和 Ashish 在一棵无根树上玩游戏，这棵树有 $n$ 个节点，编号为 $1$ 到 $n$。两位玩家轮流进行如下操作：

• 选择树中的任意一个叶子节点，并将其与连接它的任意一条边一起移除。叶子节点指度数小于等于 $1$ 的节点。

树是一个无环连通无向图。

有一个特殊节点，编号为 $x$。移除这个节点的玩家获胜。

Ayush 先手。如果双方都采取最优策略，判断谁会获胜。

输入格式

输入的第一行为一个整数 $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$ 之间有一条边。

输出格式

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

样例输入 1

1
3 1
2 1
3 1

样例输出 1

Ashish

样例输入 2

1
3 2
1 2
1 3

样例输出 2

Ayush

提示

对于第 $1$ 个测试用例，Ayush 只能移除节点 $2$ 或 $3$，此后节点 $1$ 变为叶子节点，Ashish 可以在他的回合移除它。

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