← 返回题目列表

Codeforces · 1363/C

C. 叶子上的游戏

中文机器翻译题面 查看原题

Ayush 和 Ashish 在一棵无根树上玩游戏,该树由编号为 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 个节点组成。玩家轮流做出以下动作:

- 选择树中的任何叶节点,并将其与将此节点作为其端点之一的任何边一起删除。叶节点是度数小于或等于$$$1$$$的节点。

树是无环的连通无向图。

有一个特殊节点,编号为$$$x$$$。移除该节点的玩家赢得游戏。

阿尤什先行动。如果每个玩家都发挥最佳,则确定游戏的获胜者。

输入

输入的第一行包含一个整数 $$$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, \text{ } 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$$$st测试用例,Ayush只能删除节点$$$2$$$或$$$3$$$,之后节点$$$1$$$成为叶节点,Ashish可以轮流删除它。

对于 $$$2$$$nd 测试用例,Ayush 可以在第一步中删除节点 $$$2$$$。