Problem Description

AtCoder Inc. is a company consisting of $N$ islands numbered from $0$ to $N-1$. These islands are connected by $N-1$ bridges numbered from $0$ to $N-2$. Bridge $i$ connects island $A_i$ and island $B_i$ bidirectionally. It is possible to reach any island from any other island by crossing these bridges.

All islands have hotels, but currently, all hotels are closed. Takahashi, the responsible person from the tourism department of AtCoder, has planned a schedule for reopening and closing the hotels over the next $Q$ days. Specifically, on the morning of day $i$ ($0 \leq i \leq Q-1$), the following happens:

• If the hotel on island $X_i$ is closed, it resumes operations.
• If the hotel on island $X_i$ is open, it closes.

It is guaranteed that for all $i$ ($0 \leq i \leq Q-1$), there is at least one hotel open on the day $i$ at noon.

A bridge $i$ is considered important on day $j$ if:

• There exist two islands $a$ and $b$ with open hotels on day $j$ at noon, such that to travel from island $a$ to island $b$, bridge $i$ must be crossed.

For each bridge, determine how many days out of the $Q$ days it is important.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_0 $ $ B_0 $ $ A_1 $ $ B_1 $ $\vdots$ $ A_{N-2} $ $ B_{N-2} $ $ X_0 $ $ X_1 $ $\vdots$ $ X_{Q-1} $

Output Format

Output $N-1$ lines. The $(i+1)$th ($0 \leq i \leq N-2$) line should contain the number of days out of the $Q$ days that bridge $i$ is important.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
3
3
3

Sample Input #2

15 15
10 12
7 8
2 13
4 1
11 4
6 9
3 0
5 11
8 2
12 0
2 5
6 2
5 0
0 14
14
9
3
10
13
7
1
3
1
13
7
9
10
9
3

Sample Output #2

9
5
5
2
2
12
6
2
5
9
12
12
12
13

Notes/Hints

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_i, B_i \leq N-1$
• It is possible to reach any island from any other island by crossing the bridges.
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq X_i \leq N-1$
• For all $i$ ($0 \leq i \leq Q-1$), there is at least one hotel open on day $i$ at noon.
• All input values are integers.

Sample Explanation 1

For example, on the noon of day $2$, the islands with open hotels are islands $0, 2, 4$, and the important bridges on this day are bridges $1, 2, 3$.

见题面 Input 部分

见题面 Output 部分