Unique Cities and Their Products

JOI country has \(N\) cities numbered from 1 to \(N\), connected by \(N-1\) bidirectional roads forming a tree. Each city \(j\) produces a product \(C_j\) (an integer between 1 and \(M\)). Note that not every integer between 1 and \(M\) is necessarily a product. A city \(y\) (with \(y \neq x\)) is called a unique city for city \(x\) if and only if for any other city \(z\) (where \(z \neq x\) and \(z \neq y\)), the distance between \(x\) and \(y\) is different from the distance between \(x\) and \(z\).

For each city \(x\), consider all cities that are unique with respect to \(x\) and count how many distinct products they produce. Your task is to compute this value for every city.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \leq N \leq 10^3\), \(1 \leq M \leq 10^3\)).

The next \(N-1\) lines each contain two integers \(A_i\) and \(B_i\) (\(1 \leq A_i, B_i \leq N\)), representing a bidirectional road connecting cities \(A_i\) and \(B_i\). It is guaranteed that any city is reachable from any other city.

The last line contains \(N\) integers \(C_1, C_2, \ldots, C_N\), where \(C_j\) is the product produced by city \(j\).

outputFormat

Output \(N\) lines. The \(i\)-th line should contain a single integer indicating the number of distinct products produced by the unique cities for city \(i\).

sample

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

2
1
3
1
1