Farmer John (a.k.a. FJ) has gotten bored of breeding cows, and has decided to move onto raising tarantulas on his farm to reap a gigantic profit in Spooky Season (many of his clients are Halloween pranksters). He notices that the $N$ spiders have built individual burrows (yes, tarantulas build burrows instead of webs) to live in. However, he also notices that there are $N -1$ bidirectional tunnels connecting these burrows such that any tarantula could travel from his/her nest to any other nest. It turns out that there are subspecies of tarantulas among the ones that FJ has chosen to nurture, and they are always competing amongst each other to cover the most "range" over the network of tunnels. The range of a subspecies is defined as the longest path (calculated as the number of tunnels taken) between any two burrows belonging to members of the same subspecies. If there are not at least two members of the same subspecies present on the farm, then the range of that subspecies is $0$. FJ wants to calculate the range for every subspecies present in his farm, and promises you a cut of the sales if you help him out.
The first line of input contains two integers $N$ ($1 <= N <= 200000$) and $K$ ($1 <= K <= N$) representing the number of tarantulas and the number of subspecies, respectively. The second line of input contains $N$ integers $s_i$ ($1 <= s_i <= K$) representing what subspecies the $i$-th tarantula falls under. The next $N -1$ lines each contain two integers $a$ and $b$ ($1 <= a, b <= N$) to represent a tunnel from the burrow of spider $a$ to the burrow of spider $b$.
Output $K$ lines of output, with one integer on each line representing the range of the $i$-th subspecies of tarantula.
## Input
The first line of input contains two integers $N$ ($1 <= N <= 200000$) and $K$ ($1 <= K <= N$) representing the number of tarantulas and the number of subspecies, respectively. The second line of input contains $N$ integers $s_i$ ($1 <= s_i <= K$) representing what subspecies the $i$-th tarantula falls under. The next $N -1$ lines each contain two integers $a$ and $b$ ($1 <= a, b <= N$) to represent a tunnel from the burrow of spider $a$ to the burrow of spider $b$.
## Output
Output $K$ lines of output, with one integer on each line representing the range of the $i$-th subspecies of tarantula.
[samples]
**Definitions**
Let $ N, K \in \mathbb{Z}^+ $ denote the number of tarantulas and subspecies, respectively.
Let $ s: \{1, \dots, N\} \to \{1, \dots, K\} $ be the subspecies assignment function, where $ s_i $ is the subspecies of tarantula $ i $.
Let $ T = (V, E) $ be a tree with $ |V| = N $ vertices (burrows) and $ |E| = N - 1 $ edges (tunnels), where vertex $ i $ corresponds to the burrow of tarantula $ i $.
For each subspecies $ c \in \{1, \dots, K\} $, define:
- $ V_c = \{ i \in V \mid s_i = c \} $: the set of vertices (burrows) occupied by subspecies $ c $.
- If $ |V_c| < 2 $, then the **range** of subspecies $ c $ is $ 0 $.
- Otherwise, the **range** of subspecies $ c $ is the **diameter** of the induced subtree on $ V_c $, i.e., the maximum distance (number of edges) between any two vertices in $ V_c $, computed along the unique paths in $ T $.
**Constraints**
1. $ 1 \le N \le 200000 $
2. $ 1 \le K \le N $
3. $ 1 \le s_i \le K $ for all $ i \in \{1, \dots, N\} $
4. The graph $ T $ is a tree.
**Objective**
For each subspecies $ c = 1 $ to $ K $, compute:
$$
\text{range}(c) =
\begin{cases}
0 & \text{if } |V_c| < 2 \\
\max_{u,v \in V_c} \text{dist}_T(u,v) & \text{otherwise}
\end{cases}
$$
Output $ \text{range}(1), \text{range}(2), \dots, \text{range}(K) $, one per line.