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

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

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

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

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

制約

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

小課題

1. (4 点) N \leqq 2\,000．
2. (32 点) M = 1．
3. (32 点) M = N，C_j = j (1 \leqq j \leqq N)．
4. (32 点) 追加の制約はない．

入力例 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

この入力例は小課題 2 の制約を満たす．

入力例 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

この入力例は小課題 3 の制約を満たす．

入力例 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