Помимо бинарных деревьев на парах по дискретной математике Профессор Р. также рассказывает об ориентированных деревьях. Дадим определение направленного дерева. Ориентированное (направленное) дерево — ациклический ориентированный граф, в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями. На рисунке ниже показан пример ориентированного дерева.
После занятия по ориентированным деревьям профессор задал студентам на дом следующую задачу.
Покрасим все вершины ориентированного дерева в некоторые цвета (обозначим через $$$c_i$$$ цвет вершины с номером $$$i$$$). После этого для каждой вершины $$$i$$$ профессор хочет узнать, какой цвет встречается чаще всего в поддереве, корнем которого является вершина с данным номером $$$i$$$.
Как ни старались студенты, они не смогли придумать, как решить эту задачу. Помогите им – напишите программу, которая ответит на все запросы, составленные профессором Р.
В первой строке содержатся числа $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – количество вершин в дереве.
Во второй строке содержатся $$$N$$$ чисел $$$c_i$$$ $$$(1 \le c_i \le 10^9)$$$, разделенных пробелом, – цвета вершин, $$$i$$$-е число соответствует вершине с номером $$$i$$$.
В следующих $$$N - 1$$$ строке содержатся пары чисел $$$u$$$ и $$$v$$$ $$$(1 \le u, v \le N, u \ne v)$$$, описывающие рёбра дерева. Вершина $$$u$$$ соответствует началу ребра, $$$v$$$ – его концу. Гарантируется, что граф во входных данных является ориентированным деревом. Не гарантируется, что вершина $$$1$$$ является корнем дерева.
Выведите $$$N$$$ чисел, разделенных пробелом, $$$i$$$-е число в выводе должно соответствовать цвету, который чаще всего встречается в поддереве, корнем которого является вершина $$$i$$$. Если требуемых цветов несколько, требуется вывести цвет с наименьшим значением.
81 2 3 4 5 6 7 81 31 51 66 26 76 83 4
1 2 3 4 5 2 7 8
81 2 1 1 1 2 2 21 31 51 66 26 76 83 4
1 2 1 1 1 2 2 2
Деревья во входных данных соответствуют картинке из условия.
