408321: GYM103092 G Game

G. Gameограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В SDU есть давняя традиция – собираться по выходным в университете и устраивать киномарафоны. Абу и Арс опять не могут решить какие фильмы выбрать для просмотра. Так как они устали от классического камень, ножницы, бумага, то они придумали новую интересную игру, которая разрешила бы их спор.

У игроков есть дерево из $$$n$$$ вершин и $$$n-1$$$ ребер. На одной из вершин дерева стоит фишка. А также есть список из $$$k$$$ запрещенных вершин. За свой ход Абу может удалить любое ребро из дерева. За свой ход Арс может передвинуть фишку в соседнюю вершину по любому не удаленному ребру или остаться на той же вершине. Первым ходит Абу. Игра заканчивается когда в дереве больше не осталось ребер. Арс выигрывает если в какой-то момент фишка оказалась на запрещенной вершине.

Вы заметили, что при определенных начальных условиях вы можете определить победителя. Определите кто выигрывает при оптимальной игре обоих игроков для каждой изначальной позиции фишки от $$$1$$$ до $$$n$$$.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ $$$(2 \le n \le 200000; 1 \le k \le n)$$$ - количество вершин в дереве и количество запрещенных вершин.

В следующих $$$n-1$$$ строках заданы два целых числа $$$u_i$$$ и $$$v_i$$$ $$$(1 \le u_i, v_i \le n; u_i \neq v_i)$$$ — вершины дерева, соединенные $$$i$$$-м ребром. Все заданные ребра различны и образуют дерево.

В последней строке заданы $$$k$$$ различных чисел через пробел — номера запрещенных вершин в графе.

Выходные данные

Выведите $$$n$$$ строк, где $$$i$$$-я строка будет ответом для графа в котором фишка изначально находится на $$$i$$$ вершине. В случае победы Абу, выведите строку «Abu». Иначе выведите «Ars» (без кавычек).

ПримерыВходные данные

8 3
4 3
5 4
2 5
1 5
6 5
7 5
7 8
1 3 8

Выходные данные

Ars
Abu
Ars
Abu
Abu
Abu
Abu
Ars

Входные данные

10 5
1 6
8 6
4 3
10 9
10 2
5 6
2 1
4 6
2 7
3 1 5 2 10

Выходные данные

Ars
Ars
Ars
Ars
Ars
Ars
Abu
Abu
Abu
Ars

Примечание

Разберем первый пример. Если изначально фишка будет находиться на вершине $$$2$$$, дерево будет выглядеть следующим образом (красным обозначены запрещенные вершины):

На первом ходу Абу удаляет ребро, соединяющее вершины $$$1$$$ и $$$5$$$. После хода Абу, Арс двигает фишку на вершину $$$5$$$.

На третьем ходу Абу удаляет ребро, соединяющее вершины $$$3$$$ и $$$4$$$. После хода Абу, Арс двигает фишку на вершину $$$7$$$.

На пятом ходу Абу удаляет ребро, соединяющее вершины $$$7$$$ и $$$8$$$. Так как Абу уже удалил все ребра, ведущие к запрещенным вершинам, Арс уже никак не сможет победить. Побеждает Абу.