E - Blackout 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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 番目のイベントが終わった直後に電気が通っている都市の数を出力せよ。

入力例 1

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

出力例 1

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 となります。

Score : 500 points

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

  • All values in input are integers.
  • 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
  • If i \neq j, then U_i \neq U_j or V_i \neq V_j.
  • 1 \le X_i \le E
  • X_i are distinct.

Input

Input is given from Standard Input in the following format:

N M E
U_1 V_1
U_2 V_2
\vdots
U_E V_E
Q
X_1
X_2
\vdots
X_Q

Output

Print Q lines.
The i-th line should contain the number of electrified cities right after the i-th event.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

  • The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
    • Now City 5 is no longer electrified, while 4 cities remain electrified.
  • The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
  • The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
    • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
  • The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
  • The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
  • The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
    • Now City 1 is no longer electrified, while 1 city remains electrified.