Дано дерево, состоящее из $$$2n$$$ вершин. Напомним, что деревом называется связный неориентированный граф, в котором нет циклов. На каждой вершине написано одно целое число от $$$1$$$ до $$$n$$$. Каждое число от $$$1$$$ до $$$n$$$ написано ровно на двух различных вершинах. У каждой вершины также есть стоимость — вершина $$$i$$$ стоит $$$2^i$$$.
Требуется выбрать в дереве такое подмножество вершин, что:
- подмножество связно; то есть, из каждой вершины подмножества можно добраться до любой другой вершины подмножества, проходя только через вершины подмножества;
- каждое число от $$$1$$$ до $$$n$$$ написано хотя бы на одной вершине подмножества.
Среди всех таких подмножеств требуется найти такое, что суммарная стоимость вершин в нем минимальна. Обратите внимание, что не требуется минимизировать количество вершин в подмножестве.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке записаны $$$2n$$$ целых чисел $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le n$$$). Каждое число от $$$1$$$ до $$$n$$$ встречается ровно два раза.
В каждой из следующих $$$2n-1$$$ строк записаны два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le 2n$$$) — ребра дерева. Данные ребра образуют валидное дерево.
В первой строке выведите одно целое число $$$k$$$ — количество вершин в подмножестве.
Во второй строке выведите $$$k$$$ различных целых чисел от $$$1$$$ до $$$2n$$$ — номера вершин в выбранном подмножестве. Вершины можно выводить в произвольном порядке.
31 1 3 2 3 24 21 66 26 32 5
3 2 4 5
32 3 1 3 2 16 42 45 23 63 1
4 1 3 4 6
65 2 3 4 6 4 2 5 6 1 1 310 82 1012 74 105 96 21 93 412 611 54 5
6 2 3 4 5 8 10
На данных изображениях нарисованы ответы на первые два примера. В скобках около номеров вершин подписаны числа, написанные на них.
В первом примере есть такие валидные подмножества: $$$[2, 4, 5]$$$ (стоимость равна $$$2^2 + 2^4 + 2^5 = 52$$$), $$$[2, 4, 5, 6]$$$ (стоимость равна $$$116$$$), $$$[1, 6, 3]$$$ (стоимость равна $$$74$$$), $$$[2, 6, 3]$$$ (стоимость равна $$$76$$$) и многие другие.
Во втором примере стоимость подмножества $$$[4, 6, 3, 1]$$$ равна $$$90$$$.
