34226번 - 그래프와 연결성 쿼리

문제

정점이 $N$개, 간선이 $M$개인 무방향 그래프가 주어진다. 간선은 1ドル$번부터 $M$번까지 번호가 매겨져 있으며, 자기 자신으로 향하는 간선(셀프 루프)이나 중복 간선은 존재하지 않는다.

이 때 다음 쿼리를 처리하는 프로그램을 작성하시오.

• $l$ $r$: 간선 번호가 $l$번 이상 $r$번 이하인 간선들만 사용할 수 있을 때, 서로 연결되어 있는 정점 쌍 $(u, v)$ $(1 \le u < v \le N)$의 개수를 출력한다.

입력

첫 번째 줄에 정수 $N,ドル $M,ドル $Q$가 공백으로 구분되어 주어진다. $(1 \le N, M, Q \le 100,000円)$

다음 $M$개의 줄에는 간선 정보가 주어진다.

각 줄에는 두 정수 $a_i,ドル $b_i$ $(1 \le a_i, b_i \le N;\ a_i \ne b_i)$가 공백으로 구분되어 주어지며, 이는 $i$번째 간선이 정점 $a_i$와 정점 $b_i$를 잇는 무방향 간선임을 의미한다. 중복 간선은 주어지지 않는다.

그 다음 $Q$개의 줄에는 쿼리가 주어진다.

각 줄에는 두 정수 $l,ドル $r$ $(1 \le l \le r \le M)$가 공백으로 구분되어 주어진다.

출력

각 줄에 쿼리의 정답을 출력한다.

제한

힌트