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 |