配点 : $500$ 点

問題文

ある国には $N$ 個の都市と $M$ 個の発電所があります。これらを総称して地点と呼びます。 地点には $1,2,\dots,N+M$ の番号がつけられており、そのうち都市は地点 $1,2,\dots,N$ で発電所は地点 $N+1,N+2,\dots,N+M$ です。

この国には電線が $E$ 本あり、電線 $i$ ( $1 \le i \le E$ ) は地点 $U_i$ と地点 $V_i$ を双方向に結びます。 また、ある都市に 電気が通っている とは、ある都市から電線をいくつか辿って少なくともひとつの発電所に辿り着くことができる状態を言います。

今、 $Q$ 個のイベントが起こります。そのうち $i$ ( $1 \le i \le Q$ ) 番目のイベントでは電線 $X_i$ が切れ、その電線を辿ることができなくなります。一度切れた電線は、その後のイベントにおいても切れたままです。

全てのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めてください。

制約

• 入力は全て整数
• $1 \le N,M$
• $N+M \le 2 \times 10^5$
• $1 \le Q \le E \le 5 \times 10^5$
• $1 \le U_i < V_i \le N+M$
• $i \neq j$ ならば、 $U_i \neq U_j$ または $V_i \neq V_j$
• $1 \le X_i \le E$
• $X_i$ は相異なる

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $E$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_E$ $V_E$

$Q$

$X_1$

$X_2$

$\vdots$

$X_Q$

出力

$Q$ 行出力せよ。 そのうち $i$ ( $1 \le i \le Q$ ) 行目には $i$ 番目のイベントが終わった直後に電気が通っている都市の数を出力せよ。

5 5 10
2 3
4 10
5 10
6 9
2 9
4 8
1 7
3 6
8 10
1 8
6
3
5
8
10
2
7

4
4
2
2
2
1

はじめ、全ての都市に電気が通っています。

• $1$ 番目のイベントによって地点 $5$ と地点 $10$ を結ぶ電線 $3$ が切れます。- これにより、都市 $5$ に電気が通らなくなり、電気が通っている都市の数は $4$ となります。
• $2$ 番目のイベントによって地点 $2$ と地点 $9$ を結ぶ電線 $5$ が切れます。
• $3$ 番目のイベントによって地点 $3$ と地点 $6$ を結ぶ電線 $8$ が切れます。- これにより、都市 $2,3$ に電気が通らなくなり、電気が通っている都市の数は $2$ となります。
• $4$ 番目のイベントによって地点 $1$ と地点 $8$ を結ぶ電線 $10$ が切れます。
• $5$ 番目のイベントによって地点 $4$ と地点 $10$ を結ぶ電線 $2$ が切れます。
• $6$ 番目のイベントによって地点 $1$ と地点 $7$ を結ぶ電線 $7$ が切れます。- これにより、都市 $1$ に電気が通らなくなり、電気が通っている都市の数は $1$ となります。