問題文

AtCoder 株式会社は、0 から N-1 までの番号のついた N 個の島からなる会社です。 これらの島は、0 から N-2 までの番号のついた N-1 個の橋によって結ばれています。 橋 i は、島 A_i と島 B_i を双方向に結んでいます。 どの島からどの島へも、橋を渡っていくことでたどり着くことができます。

全ての島にはホテルがあります。 しかし現在、全てのホテルは営業休止中です。 そこで、AtCoder の観光部門の担当者である高橋くんは、これから Q 日間にわたるホテルの営業再開、休止の計画を立てました。 具体的には、i (0 \leq i \leq Q-1) 日目の朝に、以下のことが起こります。

• 島 X_i のホテルが営業休止している場合、そのホテルの営業を再開する。
• 島 X_i のホテルが営業している場合、そのホテルの営業を休止する。

なお、全ての i (0 \leq i \leq Q-1) について、i 日目の昼に営業しているホテルが 1 つ以上あることが保証されます。

橋 i が j 日目に重要であるとは、以下のことを意味します。

• j 日目の昼にホテルが営業している 2 つの島 a,b であって、島 a から島 b へ向かうためには橋 i を通らなければならないものが存在する。

それぞれの橋について、その橋が重要である日が Q 日間のうち何日あるか求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i,B_i \leq N-1
• どの島からどの島へも、橋を渡っていくことでたどり着くことができる。
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq X_i \leq N-1
• 全ての i (0 \leq i \leq Q-1) について、i 日目の昼に営業しているホテルが 1 つ以上存在する。
• 入力される値はすべて整数である。

入力例 1

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

出力例 1

2
3
3
3

例えば、2 日目の昼にホテルが営業している島は 島 0,2,4 であり、この日に重要な橋は 橋 1,2,3 です。

入力例 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

出力例 2

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