Найнижчий найвищий спільний предок

Limits: 4 sec., 256 MiB

У Зеника із Марічкою є кореневе дерево — орієнтований ациклічний граф із \(n\) вершин (пронумерованих цілими числами від 1 до \(n\)) та \(n-1\) ребер із коренем у вершині 1. Із кореня можна дістатись до усіх інших вершин по ребрах.

Окрім цього, \(i\)-та вершина (\(1 \le i \le n\)) пофарбована у \(c_i\)-й колір. Кожен колір покриває зв’язну область дерева, тобто для кожного кольору існує вершина, пофарбована в цей колір, з якої можна дійти по ребрах до усіх інших вершин цього кольору, не відвідуючи інші кольори.

Висотою вершини \(i\) будемо вважати кількість ребер, які потрібно пройти на шляху від кореня (вершини 1) до вершини \(i\).

Марічка хоче вибрати множину кольорів та передати Зенику на опрацювання усі вершини, колір яких належить вибраній множині. Позначимо як \(S\) множину усіх вершин, які отримає Зеник.

Зеник своєю чергою знайде найбільшу висоту вершини, із якої можна дістатись до усіх вершин множини \(S\), і поверне Марічці одне ціле число — висоту цієї вершини. Зауважте, що вибрана Зеником вершина не обов’язково повинна бути в \(S\).

Ваше завдання — для кожного \(k\) від 1 до \(n\) включно визначити, яке найменше число може повернути Зеник Марічці, якщо розмір множини вершин \(S\), яку він отримає, рівний \(k\). Якщо вибрати множину кольорів, яка утворює \(k\) вершин неможливо, виведіть -1.

Input

У першому рядку задано одне ціле число \(n\) — кількість вершин дерева.

У другому рядку задано \(n\) цілих чисел \(c_i\) — кольори відповідних вершин.

У наступних \(n-1\) рядках задано пари цілих чисел \(u_i\) та \(v_i\) через пробіл — орієнтовані ребра дерева (\(u_i \rightarrow v_i\)).

Output

У єдиному рядку виведіть \(n\) цілих чисел — відповіді на задачу для \(k\) від 1 до \(n\), включно.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le c_i \le n\),

\(1 \le u_i < v_i \le n\),

Заданий граф є орієнтованим деревом із коренем у вершині 1.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 1 1 3 1 2 4 1 2 2 3 2 4 2 5 3 6 5 7	2 1 1 0 0 0 0

Input (stdin) сopy	Output (stdout) сopy
14 1 1 1 2 1 1 1 1 2 2 3 4 5 1 1 2 1 3 1 4 4 9 4 10 10 11 10 12 2 7 2 6 12 13 8 14 5 8 3 5	3 2 1 1 1 1 -1 0 0 0 0 0 0 0