Game On Leaves
Description
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.
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.
For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).
Input
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.
Output
For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).
Samples
1
3 1
2 1
3 1
Ashish
1
3 2
1 2
1 3
Ayush
Note
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.