珍しい都市(Unique Cities)

JOI 国には$N$ 個の都市があり，1 から$N$ までの番号がついている．これらの都市は$N - 1$ 本の道路で結ばれている．$i$ 番目($1 \leq i \leq N - 1$) の道路は都市$A_i$ と都市$B_i$ を結んでおり，双方向に通行可能である．どの都市からどの都市へも何本かの道路を通行することで移動できる．

JOI 国にはいくつかの特産品が存在する．特産品には，種類を表す1 以上$M$ 以下の番号が付けられている(JOI 国で生産されている特産品に対応していない番号があるかもしれない)．各都市は1 つの特産品を生産しており，都市$j$ ($1 \leq j \leq N$) では特産品$C_j$ を生産している．複数の都市が同じ種類の特産品を生産することがあるかもしれない．

2 つの都市の間の距離は，その間を移動するために通る道路の本数の最小値である．都市$x$ ($1 \leq x \leq N$)から見て都市$y$ ($1 \leq y \leq N, y \ne x$) が珍しい都市であるとは，すべての都市$z$ ($1 \leq z \leq N, z \ne x, z \ne y) について，都市$x, y$ 間の距離と都市$x, z$ 間の距離が異なることを意味する．

JOI 国の大臣であるK 理事長は，すべての$j$ ($1 \leq j \leq N$) について，都市$j$ から見て珍しい都市で生産されている特産品が何種類あるかを知りたい．

JOI 国の道路の情報と，各都市で生産されている特産品の番号が与えられたとき，各都市ごとに，その都市から見て珍しい都市で生産されている特産品が何種類あるかを求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$
$A_1$ $B_1$
:
$A_{N-1}$ $B_{N-1}$
$C_1$ ... $C_N$

出力

標準出力に$N$ 行で出力せよ． $j$ 行目($1 \leq j \leq N$) には，都市$j$ から見て珍しい都市で生産されている特産品が何種類あるかを出力せよ．

制約

• $ 2 \leq N \leq 200 000$．
• $ 1 \leq M \leq N$．
• $ 1 \leq A_i \leq N (1 \leq i \leq N - 1)，1 \leq B_i \leq N (1 \leq i \leq N - 1)$．
• $ A_i \ne B_i (1 \leq i \leq N - 1)$．
• どの都市からどの都市へも何本かの道路を通行することで移動できる．
• $ 1 \leq C_j \leq M (1 \leq j \leq N)$．

入出力例

入力例1

5 4
1 2
2 3
3 4
3 5
1 2 1 2 4

出力例1

2
0
1
1
1

都市1 から見て珍しい都市は都市2; 3 であり，そこで生産される特産品は特産品2; 1 なので，答えは2種類である．

都市2 から見て珍しい都市は存在しないので，答えは0 種類である．

都市3 から見て珍しい都市は都市1 であり，そこで生産される特産品は特産品1 なので，答えは1 種類である．

都市4 から見て珍しい都市は都市1; 3 であり，どちらの都市においても生産される特産品は特産品1 なので，答えは1 種類である．

都市5 から見て珍しい都市は都市1; 3 であり，どちらの都市においても生産される特産品は特産品1 なので，答えは1 種類である．

番号3 の特産品は存在しないことに注意せよ．

入力例2

7 1
1 2
2 3
3 4
4 5
5 6
6 7
1 1 1 1 1 1 1

出力例2

1
1
1
0
1
1
1

入力例3

10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10

出力例3

4
3
4
2
0
2
2
0
3
2

入力例4

22 12
9 6
12 13
4 20
21 22
3 19
2 9
6 18
18 11
18 3
16 2
6 4
3 17
16 10
8 16
22 1
16 14
15 8
9 21
2 12
21 5
12 7
1 1 4 8 4 11 7 6 7 11 6 11 10 4 7 5 3 12 9 6 12 2

出力例4

2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0

情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』

---