Đất nước JOI có \(N\) thành phố, đánh số từ \(1\) đến \(N\), được nối với nhau bởi \(N-1\) con đường. Con đường thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\), cho phép đi lại theo cả hai chiều. Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường này.

Đất nước JOI có một số loại đặc sản địa phương. Mỗi loại đặc sản được gán một số nguyên từ \(1\) đến \(M\); một số số nguyên trong khoảng này có thể không tương ứng với loại đặc sản nào. Mỗi thành phố sản xuất đúng một loại đặc sản. Thành phố \(j\) sản xuất đặc sản \(C_j\). Nhiều thành phố có thể sản xuất cùng một loại đặc sản.

Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để đến thành phố này từ thành phố kia. Với một thành phố \(x\), một thành phố \(y \ne x\) được gọi là thành phố độc nhất đối với \(x\) nếu với mọi thành phố \(z\) khác cả \(x\) và \(y\), khoảng cách từ \(x\) đến \(y\) khác khoảng cách từ \(x\) đến \(z\). Nói cách khác, không có thành phố nào khác có cùng khoảng cách đến \(x\) như \(y\).

Ông K, Bộ trưởng Giao thông của đất nước JOI, muốn biết với mỗi thành phố \(j\), có bao nhiêu loại đặc sản khác nhau được sản xuất tại các thành phố độc nhất đối với \(j\).

Hãy tính các giá trị này từ thông tin về đường sá và đặc sản của từng thành phố.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

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

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(j\) chứa số loại đặc sản khác nhau được sản xuất tại các thành phố độc nhất đối với thành phố \(j\).

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(2 \le N \le 200000\).
• \(1 \le M \le N\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với \(1 \le i \le N-1\).
• Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường đã cho.
• \(1 \le C_j \le M\) với \(1 \le j \le N\).

Phân nhóm

Các điều kiện về đường sá và phạm vi \(C_j\) trong phần ràng buộc chung áp dụng cho mọi nhóm.

1. \(4\) điểm: \(2 \le N \le 2000\), \(1 \le M \le N\).
2. \(32\) điểm: \(2 \le N \le 200000\), \(M=1\), \(C_j=1\) với mọi \(1 \le j \le N\).
3. \(32\) điểm: \(2 \le N \le 200000\), \(M=N\), \(C_j=j\) với mọi \(1 \le j \le N\).
4. \(32\) điểm: \(2 \le N \le 200000\), \(1 \le M \le N\).

Ví dụ

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

2
0
1
1
1

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

1
1
1
0
1
1
1

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

4
3
4
2
0
2
2
0
3
2

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

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

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 5. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.