E2. Игра (сложная версия)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно найти все возможные вершины, которые может выбрать Чирно. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Чирно и Дайёсей играют в игру с деревом$$$^{\text{∗}}$$$ из $$$n$$$ вершин, корнем которого является вершина $$$1$$$. Значение $$$i$$$-й вершины равно $$$w_i$$$. Они по очереди делают ходы; первым ходит Чирно.

На каждом ходу, предполагая, что противник выбрал $$$j$$$ на последнем ходу, игрок может выбрать любую оставшуюся вершину $$$i$$$, удовлетворяющую условию $$$w_i>w_j$$$, и удалить поддерево$$$^{\text{†}}$$$ вершины $$$i$$$. В частности, Чирно может выбрать любую вершину и удалить её поддерево на первом ходу.

Первый игрок, который не может сделать ход, выигрывает, и они оба надеются победить. Найдите все возможные вершины, которые может выбрать Чирно на первом ходу, чтобы выиграть, если оба игрока будут играть оптимально.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Вершина $$$u$$$ принадлежит поддереву вершины $$$i$$$, если любой путь от $$$1$$$ до $$$u$$$ проходит через $$$i$$$.

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

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — количество вершин в дереве.

Вторая строка содержит $$$n$$$ целых чисел $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le n$$$) — значения вершин.

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

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

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

Для каждого набора входных данных выведите одну строку.

Если Чирно может выиграть, выведите несколько чисел. Первое число $$$k$$$ обозначает количество возможных вершин, которые она может выбрать на первом ходу. Следующие $$$k$$$ чисел обозначают данные вершины в порядке возрастания.

В противном случае выведите «0» (без кавычек).

Пример
Входные данные
5
4
2 2 4 3
1 2
1 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 2 3
1 2
1 3
5
3 1 3 4 5
1 2
2 3
3 4
4 5
10
1 2 3 2 4 3 3 4 4 3
1 4
4 6
7 4
6 9
6 5
7 8
1 2
2 3
2 10
Выходные данные
2 2 4
0
1 2
1 2
5 3 4 6 7 10
Примечание

В первом наборе входных данных:

  1. Если Чирно выберет $$$1$$$ или $$$3$$$ на первом ходу, Дайёсей не сможет сделать ход, поэтому Дайёсей выигрывает.
  2. Если Чирно выберет $$$2$$$ или $$$4$$$ на первом ходу, Дайёсей сможет выбрать только $$$3$$$, но после этого Чирно не сможет сделать ход, поэтому Чирно выигрывает.

Таким образом, все возможные вершины, которые может выбрать Чирно — это $$$2$$$ и $$$4$$$.

Во втором наборе входных данных, независимо от того, какую вершину выберет Чирно, Дайёсей не сможет сделать ход, поэтому Дайёсей выигрывает.

В третьем и четвертом наборах входных данных единственной возможной вершиной, которую может выбрать Чирно на первом ходу, является $$$2$$$.

В пятом наборе входных данных все возможные вершины, которые может выбрать Чирно на первом ходу — это $$$3,4,6,7$$$ и $$$10$$$.