翻译

JOI 国有 $N$ 个城市，编号从 $1$ 到 $N$。这些城市之间由 $N-1$ 条道路相连。第 $i$ 条道路（$1 \leqq i \leqq N-1$）连接了城市 $A_i$ 和城市 $B_i$，可以双向通行。通过几条道路可以从任意一个城市到达另一个城市。

JOI 国拥有一些特产。每个特产都被分配了一个编号，范围从 $1$ 到 $M$（可能存在一些编号未对应JOI国生产的特产）。每个城市生产一种特产，城市 $j$ （$1 \leqq j \leqq N$）生产特产 $C_j$。可能有多个城市生产相同类型的特产。

两个城市之间的距离定义为通过最少的道路数到达目的地。对于城市 $x$ （$1 \leqq x \leqq N$），如果对于所有城市 $z$ ($1 \leqq z \leqq N, z \neq x, z \neq y$)，城市 $x$ 与城市 $y$ 之间的距离和城市 $x$ 与城市 $z$ 之间的距离不同，则称城市 $y$ 是城市 $x$ 的稀有城市。

作为JOI国的首席部长，理事长想知道对于所有的 $j$ （$1 \leqq j \leqq N$），从城市 $j$ 出发，有多少种稀有城市生产了特产。

给定JOI国的道路信息和每个城市生产的特产编号，编写一个程序，对每个城市计算从该城市出发，有多少种稀有城市生产了特产。

---

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $C_1$ $\cdots$ $C_N$

输出

在标准输出中以 $N$ 行的形式输出。第 $j$ 行 ($1 \leqq j \leqq N$) 输出从城市 $j$ 出发，有多少种稀有城市生产了特产。

---

约束条件

• $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