Условие:
Великое Граильское дерево стоит в королевстве уже 315 лет. Оно занимает очень много места, потому король Ила решил от него избавиться как можно скорее. Само дерево представляет из себя ацикличный, связный и неориентированный граф из n вершин, каждая из которых имеет свое значение av. Избавляться от дерева возможно следующим образом:
Обозначим Sv как сумму значений всех оставшихся соседей v, если у v не осталось соседей, то Sv равна 0. Выберите вершину v, для которой av и Sv отличаются по четности (т.е. либо av четно и Sv нечетно, либо av нечетно и Sv четно). Если таких вершин нет, прекратите процесс.
Удалите вершину v и все ребра, соединенные с ней, из дерева.
Ваша задача — определить, существует ли последовательность удалений, которая приведет к полному удалению Граильского дерева (т.е. в дереве не останется вершин). Если ответ существует, выведите последовательность из n вершин в порядке их удаления. Если существует несколько ответов, выведите любой из них.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤104) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит число n (1≤n≤2⋅105) — количество вершин в Граильском дереве.
Вторая строка описывает массив a (1≤ai≤109) — значения вершин в дереве.
Далее идет n−1 строка, в каждой из которых по 2 числа v и u (1≤v,u≤n,v≠u), обозначающие что вершины v и u связаны ребром в дереве.
Гарантируется, что сумма n по всем наборам входных данных не превышает 2⋅105.
Выходные данные
Для каждого набора входных данных выведите «YES», если возможно полностью удалить Граильское дерево. В противном случае выведите «NO». Если ответ это «YES», выведите любую последовательность удалений.
