あなたは$N$棟の山小屋と、山小屋の間をつなぐ道を管理しています。山小屋にはそれぞれ$1$から$N$までの番号がついています。道は全部で$N-1$本あります。どの道も同じ長さで、どちらの方向にも通ることができます。また、どの山小屋からでも、いくつかの道を通っていくことで他のどの山小屋にも到達できます。
すべての山小屋には目印となる色が塗ってあります。登山者が同じ色の山小屋の間を移動できるように、どの山小屋にもその色と同じ色をした他の山小屋が少なくとも1つあります。あなたは、それぞれの山小屋について、その山小屋と同じ色の他の山小屋の中で最短の移動距離で到達できる山小屋を求めようとしています。
山小屋の色と、山小屋同士を直接つなぐ道の情報が与えられる。それぞれの山小屋について、その山小屋と同じ色の他の山小屋の中から移動距離が最短のものを見つけ、その最短の移動距離を出力するプログラムを作成せよ。ただし、道の長さはすべて1とする。
入力は以下の形式で与えられる。
$N$
$c_1$
$c_2$
:
$c_N$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_{N-1}$ $t_{N-1}$
１行目に山小屋の数$N$ ($2 \leq N \leq 200,000$)が与えられる。続く$N$行に$i$番目の山小屋の色$c_i$ ($1 \leq c_i \leq N$)が整数で与えられる。続く$N-1$行に、２つの山小屋を直接つなぐ道の情報が与えられる。$s_i$と$t_i$ ($1 \leq s_i < t_i \leq N$)は$i$番目の道がつなぐ２つの山小屋の番号である。ただし、どの２つの山小屋についても、それらを直接つなぐ道は１本以下とする。
出力は$N$行である。山小屋$i$について、同じ色の他の山小屋の中から移動距離が最短のものを見つけ、その最短の移動距離をi行目に出力する。
8 1 2 3 3 2 2 3 1 1 2 1 3 2 4 2 5 4 6 5 7 7 8
4 1 3 3 1 2 3 4