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