Lowest Highest Common Ancestor

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenik and Marichka have a rooted tree — a directed acyclic graph with \(n\) vertices (numbered with integers from 1 to \(n\)) and \(n-1\) edges, rooted at vertex 1. All other vertices can be reached from the root along the edges.

In addition, the \(i\)-th vertex (\(1 \le i \le n\)) is colored with color \(c_i\). Each color covers a connected region of the tree, meaning that for each color there exists a vertex colored in this color from which one can reach all other vertices of this color along the edges without visiting other colors.

The height of vertex \(i\) is defined as the number of edges that need to be traversed on the path from the root (vertex 1) to vertex \(i\).

Marichka wants to choose a set of colors and give Zenik all vertices whose color belongs to the chosen set for processing. Let \(S\) denote the set of all vertices that Zenik receives.

Zenik, in turn, will find the maximum height of a vertex from which all vertices of the set \(S\) can be reached, and return a single integer to Marichka — the height of this vertex. Note that the vertex chosen by Zenik does not necessarily have to be in \(S\).

Your task is to determine for each \(k\) from 1 to \(n\) inclusive, the minimum number Zenik can return to Marichka if the size of the set of vertices \(S\) he receives is equal to \(k\). If it is impossible to choose a set of colors that forms \(k\) vertices, output -1.

Input

The first line contains a single integer \(n\) — the number of vertices in the tree.

The second line contains \(n\) integers \(c_i\) — the colors of the corresponding vertices.

The next \(n-1\) lines contain pairs of integers \(u_i\) and \(v_i\) separated by a space — directed edges of the tree (\(u_i \rightarrow v_i\)).

Output

In a single line, output \(n\) integers — the answers to the problem for \(k\) from 1 to \(n\), inclusive.

Constraints

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

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

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

The given graph is a directed tree rooted at vertex 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