다리 찾기

무방향 그래프는 그래프 이론의 기본 개념이다. 그래프 이론은 수학과 컴퓨터 과학의 한 분야다. 무방향 그래프는 방향이 없는 간선으로 연결된 정점들의 집합을 나타내는 자료 구조다. 무방향 그래프에서 정점 $u$에서 $v$로 가는 간선이 있으면 정점 $v$에서 $u$로 가는 간선도 있다. 이런 무방향 간선은 두 원소로 이루어진 집합 $\{A,B\}$로 나타낸다. 임의의 두 정점 사이에 간선이 최대 하나뿐이면 그 무방향 그래프는 단순하다.

그래프 이론에서 연결 요소는 간선을 따라 어느 정점에서든 다른 어느 정점으로 갈 수 있는 정점과 간선의 묶음이다. 다리는 무방향 그래프의 간선 중 제거하면 연결 요소의 수가 늘어나는 간선이다.

다리는 그래프 분석에서 중요하다. 네트워크 설계, 결함 허용, 연결성 분석에 쓰인다. 다리는 네트워크의 약한 지점을 가리킨다. 다리를 제거하면 일부 성분이 고립되거나 연결이 끊어질 수 있기 때문이다. 그래프에서 다리를 찾는 알고리즘은 여러 가지가 있으며, 이를 이용해 네트워크나 시스템의 견고성과 구조를 파악한다.

정점 집합이 $V=\{1,2,\dots ,n\}$이고 간선 집합이 $E=\{\{u_1,v_1\}, \dots ,\{u_m, v_m\}\}$인 단순 무방향 그래프가 있다. 친구 Flora가 간선 $e_1, e_2, \dots , e_q$를 차례로 제거해 달라고 부탁했다. 간선을 하나 제거할 때마다 그래프에 남은 다리의 수를 보고하는 프로그램을 작성하라.

첫 줄에 공백으로 구분된 음이 아닌 정수 $n$, $m$, $q$가 주어진다. $n$은 정점의 수, $m$은 간선의 수, $q$는 제거할 간선의 수다.

다음 $m$개 줄의 $i$번째 줄에는 $E$의 $i$번째 원소를 나타내는 양의 정수 $u_i$와 $v_i$가 공백으로 구분되어 주어진다.

그다음 $q$개 줄이 주어진다. $j$번째 줄에는 $j$번째로 제거할 간선 $e_j$가 $\{x_j,y_j\}$임을 나타내는 양의 정수 $x_j$와 $y_j$가 공백으로 구분되어 주어진다.

$q$개의 줄을 출력한다. $k$번째 줄에는 처음 $k$개의 간선을 제거한 뒤 그래프에 남아 있는 다리의 수 $b_k$를 출력한다.

• $1< n \le 200000$
• $1\le m \le \min\left(200000,{n \choose 2}\right)$
• $1\le q \le m$
• 간선 $\{u,v\}$는 "$u$ $v$" 또는 "$v$ $u$" 두 가지 형식으로 주어질 수 있다.
• $\{x_i, y_i\}$는 항상 $E$에 있는 간선이다.
• 같은 간선을 두 번 제거하지 않는다.