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

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


-----Examples-----
Input
1
3 1
2 1
3 1

Output
Ashish

Input
1
3 2
1 2
1 3

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

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, x = list(map(int, input().split()))
    x -= 1

    degree = [0] * n
    edges = [(0,0)]*(n-1)
    for i in range(n - 1):
        u, v = list(map(int, input().split()))
        edges[i] = (u-1,v-1)
        degree[u-1] += 1
        degree[v-1] += 1

    if degree[x] == 1 or degree[x] == 0:
        print('Ayush')
    else:
        print('Ashish' if n % 2 else 'Ayush')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
  n,x = map(int,input().split())
  ab = [list(map(int,input().split())) for i in range(n-1)]
  graph = [[] for i in range(n+1)]
  for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
  if len(graph[x]) == 1 or n == 1:
    print("Ayush")
    continue
  if n%2:
    print("Ashish")
  else:
    print("Ayush")

from collections import Counter
T = int(input().strip())
for t in range(T):
    hh = Counter()
    n, x = list(map(int, input().split()))
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        hh[a] += 1
        hh[b] += 1
    if hh[x] <=1:
        print('Ayush')
    elif n % 2:
        print('Ashish')
    else:
        print('Ayush')


T = int(input())
for _ in range(T):
    N, s = map(int, input().split())
    s -= 1
    X = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        X[a].append(b)
        X[b].append(a)
    
    if len(X[s]) <= 1:
        print("Ayush")
        continue
    
    if (N - 3) % 2:
        print("Ayush")
    else:
        print("Ashish")

class Node:
    def __init__(self):
        self.adj = []

def solve():
    n, x = list(map(int, input().split()))
    x -= 1
    nodes = [Node() for _ in range(n)]

    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        nodes[u].adj.append(v)
        nodes[v].adj.append(u)

    if len(nodes[x].adj) == 1 or n == 1:
        return "Ayush"

    return 'Ashish' if n % 2 == 1 else 'Ayush'


t = int(input())

for _ in range(t):
    print(solve())


for t in range(int(input())):
    n, x = map(int,input().split())
    nm = 0
    for i in range(n - 1):
        a,b = map(int,input().split())
        if a == x: nm += 1
        elif b == x: nm += 1
    if nm < 2:
        print("Ayush")
    else:
        if n % 2:
            print("Ashish")
        else:
            print("Ayush")

for _ in range(int(input())):
    n, x = list(map(int, input().split()))
    neighbors = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = list(map(int, input().split()))
        neighbors[u-1].append(v-1)
        neighbors[v-1].append(u-1)
    x-=1

    if len(neighbors[x]) < 2:
        print("Ayush")
        continue

    if n % 2 == 1:
        print("Ashish")
    else:
        print("Ayush")


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n,x=list(map(int,input().split()))
    ANS=0
    
    for i in range(n-1):
        u,v=list(map(int,input().split()))
        if u==x or v==x:
            ANS+=1

    if ANS<=1:
        print("Ayush")
        continue

    if n%2==0:
        print("Ayush")
    else:
        print("Ashish")
        


t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    adj=[[] for i in range(n+1)]
    for i in range(n-1):
        u,v=map(int,input().split())
        adj[u].append(v)
        adj[v].append(u)
    if n<=2:
        print("Ayush")
    else:
        if len(adj[x])<=1:
            print("Ayush")
        else:
            if n&1:
                print('Ashish')
            else:
                print("Ayush")