Jogo nas Folhas

Ayush e Ashish jogam um jogo em uma árvore não enraizada que consiste em $n$ nós numerados de $1$ a $n$. Os jogadores fazem o seguinte movimento em turnos:

• Selecione qualquer folha da árvore e remova-a da árvore. Remova também a aresta que tinha essa folha como um de seus nós. Uma folha é um nó com grau menor ou igual a $1$.

Uma árvore é um grafo conexo acíclico não direcionado.

Há um nó especial $x$. O jogador que remover este nó ganha o jogo.

Ayush se move primeiro. Determine o vencedor do jogo se cada jogador jogar da maneira ótima.

Entrada:

A primeira linha da entrada contém um único número inteiro $t$ - o número de casos de teste.

A primeira linha de cada caso de teste contém dois números inteiros $n$ e $x$  - o número de nós na árvore e o nó especial, respectivamente.

Cada uma das próximas $n-1$ linhas contém dois números inteiros $u, v$, significando que há uma aresta entre os nós $u$ e $v$ na árvore.

Saída:

Para cada caso de teste, se Ayush vencer o jogo, imprima "Ayush", caso contrário, imprima "Ashish" (sem aspas).

Restrições:

• $1 \leq t \leq 10$;
• $1 \leq x \leq n \leq 1000$;
• $1 \leq u, v \leq n, u \neq v$.

Exemplo:

Entrada	Saida
2 3 1 2 1 3 1 3 2 1 2 1 3	Ashish Ayush

Para submeter sua solução, use esse link.