A13526. Game On Leaves

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).

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.