Codeforces Round 646 (Div. 2) |
---|
Закончено |
Ayush и Ashish играют в игру на некорневом дереве, состоящем из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Игроки делают следующий ход по очереди:
Дерево — это связный неориентированный граф без циклов.
Дана специальная вершина с номером $$$x$$$. Игрок, который удаляет эту вершину, выигрывает игру.
Ayush ходит первым. Определите победителя игры, если каждый игрок играет оптимально.
В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1 \leq t \leq 10)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ $$$(1\leq n \leq 1000, 1 \leq x \leq n)$$$ — количество вершин в дереве и специальную вершину, соответственно.
Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, что означает, что между вершинами $$$u$$$ и $$$v$$$ есть ребро.
Для каждого набора входных данных, если побеждает Ayush, выведите "Ayush", иначе выведите "Ashish" (без кавычек).
1 3 1 2 1 3 1
Ashish
1 3 2 1 2 1 3
Ayush
В первом наборе входных данных Ayush может удалить только вершину $$$2$$$ или $$$3$$$, после чего вершина $$$1$$$ становится листом, и Ashish может удалить ее в свою очередь.
Во втором наборе входных данных Ayush может удалить вершину $$$2$$$ на самом первом шаге.
Название |
---|