간선 파괴

승현이는 전국 정보 올림피아드 본선을 앞두고 그래프 이론을 공부한다. 요즘은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 푹 빠져서, 정점 $V$개와 간선 $E$개로 이루어진 무향 그래프의 컴포넌트 수를 세는 문제를 붙잡고 있다. 정점에는 $1, 2, \dots, V$의 번호를, 간선에는 $1, 2, \dots, E$의 번호를 붙였고, 같은 두 정점을 잇는 간선은 많아야 하나다.

무향 그래프가 간선으로 이어지지 않은 여러 덩어리로 나뉘어 있을 때, 서로 이어진 정점의 부분집합 하나하나를 컴포넌트라고 한다. 아래 [그림 1]에서는 {1, 2, 5, 8}, {3}, {4, 6, 7}이 각각 컴포넌트다. [그림 2]처럼 그래프 전체가 컴포넌트 하나일 수도 있다.

승현이는 문제를 보자마자 DFS로 올바른 코드를 짰지만 0점을 받았다. 선생님이 "재귀 함수를 썼다"며 채점조차 하지 않았기 때문이다. 화가 난 승현이는 destroy(l, r) 함수로 $l, l+1, \dots, r$번 간선을 한꺼번에 파괴하기 시작했다. 번호가 연속인 이유는 그래야 파괴하기 편해서라고 한다.

[그림 3] 간선 위에 적힌 빨간 번호가 그 간선의 번호다. 승현이가 destroy(3, 5)를 호출해 3, 4, 5번 간선이 파괴됐다.

여러분은 재귀 없이도 컴포넌트 수를 셀 수 있으니, 간선이 파괴된 그래프의 컴포넌트 수를 구한 다음 recover(l, r)로 파괴된 간선을 되돌려 놓아 승현이를 약올리려 한다.

[그림 4] 파괴된 그래프의 컴포넌트 수 2를 구한 뒤 recover(3, 5)로 간선을 복구했다.

그런데 승현이가 destroy를 계속 호출하는 바람에 일일이 대응하기가 벅차졌다. 이 일을 대신 해 줄 프로그램을 작성하라.

첫째 줄에 그래프의 정점 수 $V$와 간선 수 $E$가 공백을 사이에 두고 주어진다.

이어지는 $E$개 줄 중 $i$번째 줄에는 두 정수 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. $i$번 간선이 정점 $u_i$와 $v_i$를 잇는다는 뜻이다. 그래프는 무향이고, 두 정점 사이의 간선은 많아야 하나다.

그다음 줄에 승현이가 destroy 함수를 호출한 횟수 $Q$가 주어진다. 이어지는 $Q$개 줄에는 호출마다 인자 $l$과 $r$이 공백을 사이에 두고 주어진다.

$5 \le V \le 700$, $1 \le E \le 123456$, $1 \le Q \le 50000$, $1 \le u_i, v_i \le V$, $u_i \ne v_i$, $1 \le l \le r \le E$

destroy 호출마다 $l$번부터 $r$번까지의 간선이 파괴된 그래프의 컴포넌트 수를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

승현이는 자비로워서 여러분이 그래프를 복구한 뒤에야 다음 destroy를 호출한다. 따라서 각 질의는 언제나 원래 그래프에서 $l$번부터 $r$번까지의 간선만 지운 그래프를 대상으로 한다.

첫 번째 예제의 그래프는 [그림 3]의 그래프와 같다.