H. Удалить Граильское дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Великое Граильское дерево стоит в королевстве уже $$$315$$$ лет. Оно занимает очень много места, потому король Ила решил от него избавиться как можно скорее. Само дерево представляет из себя ацикличный, связный и неориентированный граф из $$$n$$$ вершин, каждая из которых имеет свое значение $$$a_v$$$. Избавляться от дерева возможно следующим образом:

  • Обозначим $$$S_v$$$ как сумму значений всех оставшихся соседей $$$v$$$, если у $$$v$$$ не осталось соседей, то $$$S_v$$$ равна $$$0$$$. Выберите вершину $$$v$$$, для которой $$$a_v$$$ и $$$S_v$$$ отличаются по четности (т.е. либо $$$a_v$$$ четно и $$$S_v$$$ нечетно, либо $$$a_v$$$ нечетно и $$$S_v$$$ четно). Если таких вершин нет, прекратите процесс.
  • Удалите вершину $$$v$$$ и все ребра, соединенные с ней, из дерева.
Ваша задача — определить, существует ли последовательность удалений, которая приведет к полному удалению Граильского дерева (т.е. в дереве не останется вершин). Если ответ существует, выведите последовательность из $$$n$$$ вершин в порядке их удаления. Если существует несколько ответов, выведите любой из них.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — количество вершин в Граильском дереве.

Вторая строка описывает массив $$$a$$$ ($$$1\le a_i\le 10^9$$$) — значения вершин в дереве.

Далее идет $$$n - 1$$$ строка, в каждой из которых по 2 числа $$$v$$$ и $$$u$$$ ($$$1\le v, u\le n, v\neq u$$$), обозначающие что вершины $$$v$$$ и $$$u$$$ связаны ребром в дереве.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите «YES», если возможно полностью удалить Граильское дерево. В противном случае выведите «NO». Если ответ это «YES», выведите любую последовательность удалений.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
3
1 2 4
1 2
2 3
4
3 4 2 1
1 2
2 3
3 4
6
9 6 5 1 7 4
1 2
2 3
2 4
3 5
4 6
5
2 1 1 1 2
2 1
3 2
2 4
5 4
5
1 5 3 7 9
1 2
2 3
3 4
4 5
Выходные данные
NO
YES
2 3 1 4 
NO
YES
1 5 2 3 4 
YES
2 4 1 5 3