Ayush и Ashish играют в игру на некорневом дереве, состоящем из \(n\) вершин, пронумерованных от \(1\) до \(n\). Игроки делают следующий ход по очереди:
- Выберите любой лист в дереве и удалите его вместе со всеми ребрами, для которых этот лист является одним из концов. Лист — это вершина со степенью, не превосходящей \(1\).
Дерево — это связный неориентированный граф без циклов.
Дана специальная вершина с номером \(x\). Игрок, который удаляет эту вершину, выигрывает игру.
Ayush ходит первым. Определите победителя игры, если каждый игрок играет оптимально.
Выходные данные
Для каждого набора входных данных, если побеждает Ayush, выведите "Ayush", иначе выведите "Ashish" (без кавычек).
Примечание
В первом наборе входных данных Ayush может удалить только вершину \(2\) или \(3\), после чего вершина \(1\) становится листом, и Ashish может удалить ее в свою очередь.
Во втором наборе входных данных Ayush может удалить вершину \(2\) на самом первом шаге.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
3 1
2 1
3 1
|
Ashish
|
|
2
|
1
3 2
1 2
1 3
|
Ayush
|