1363C · Game On Leaves

Problem: 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.

Input Format: 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 Format: For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).

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.