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$$$。