JOI 国有 $N$ 座城市，编号为 $1$ 到 $N$。这些城市由 $N-1$ 条道路连接。第 $i$ 条道路 ($1 \le i \le N-1$) 双向连接城市 $A_i$ 和 $B_i$。从任意城市出发，都可以通过某些道路到达其他任意城市。

JOI 国有一些地方特产。每种特产被分配一个 $1$ 到 $M$ 之间的整数（某些整数可能不对应 JOI 国的任何特产）。每座城市生产一种特产。城市 $j$ ($1 \le j \le N$) 生产特产 $C_j$。多座城市可能生产同一种特产。

我们将两座城市之间的距离定义为从一座城市到达另一座城市所需经过的最少道路条数。对于城市 $x$ ($1 \le x \le N$)，如果对于任意城市 $z$ ($1 \le z \le N, z \neq x, z \neq y$)，城市 $x$ 到城市 $y$ 的距离与城市 $x$ 到城市 $z$ 的距离不同，则称城市 $y$ ($1 \le y \le N, y \neq x$) 为城市 $x$ 的“唯一城市”。

JOI 国交通大臣 K 先生想知道，对于每个 $j$ ($1 \le j \le N$)，城市 $j$ 的唯一城市所生产的特产种类数。

请编写一个程序，在给定 JOI 国道路信息和每座城市生产的特产种类的情况下，计算出对于每座城市，其唯一城市所生产的特产种类数。

输入格式

从标准输入读取以下数据：

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

输出格式

向标准输出写入 $N$ 行。第 $j$ 行 ($1 \le j \le N$) 应包含城市 $j$ 的唯一城市所生产的特产种类数。

数据范围

• $2 \le N \le 200\,000$
• $1 \le M \le N$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)，$1 \le B_i \le N$ ($1 \le i \le N-1$)
• $A_i \neq B_i$ ($1 \le i \le N-1$)
• 从任意城市出发，都可以通过某些道路到达其他任意城市。
• $1 \le C_j \le M$ ($1 \le j \le N$)

子任务

1. (4 分) $N \le 2\,000$
2. (32 分) $M = 1$
3. (32 分) $M = N, C_j = j$ ($1 \le j \le 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