34255번 - 레몬레몬 왕국 서브태스크

레몬 왕국에는 $N$개의 도시와 $M$개의 도로가 있다. $i$번째 도로는 $U_i$번 도시와 $V_i$번 도시를 연결하는 양방향 도로이다. 단, $U_i < V_i$이며, 두 도시 사이에 여러 개의 도로가 존재할 수 있다. 하지만 현재 모든 도로는 노후화되어 사용할 수 없다.

기술자 재원이는 이 중 일부 도로를 정비하여 활성화하려 한다. 그런데 레몬 왕국의 왕 담유 18세는 도시의 형태가 원형이 되기를 원한다. 즉, 왕국을 정점 $N$개의 무향 그래프로 보았을 때, 각 연결 성분이 다음 조건 중 하나를 만족해야 한다.

• 성분 내 모든 정점의 차수가 $2$다. 즉, 원형 사이클이다.
• 성분의 크기가 $1$이다. 즉, 독립된 정점이다.

재원이는 담유의 명령을 따라야 하며, 비용 절감을 위해 연속된 번호의 도로들만 선택해 활성화하려 한다. 즉, 어떤 정수 쌍 $(l, r)$을 정해 $l$번 도로부터 $r$번 도로까지의 도로만을 활성화한다.

하지만 모든 경우를 직접 시도해 보면 비용이 크므로, 그는 정보과학 전문가 우현이에게 시뮬레이션을 부탁했다. $i$번째 질문에서는, $L_i \leq l \leq r \leq R_i$ 를 만족하는 순서쌍 $(l, r)$ 중 조건을 만족하는 경우의 수를 구해야 한다.

당신이 우현이가 되어, 각 질문에 대한 답을 구해보자.

입력은 다음과 같은 형식으로 주어진다.

$N \ M \ Q$

$U_1 \ V_1$

$U_2 \ V_2$

$\vdots$

$U_M \ V_M$

$L_1 \ R_1$

$L_2 \ R_2$

$\vdots$

$L_Q \ R_Q$

첫째 줄부터 $Q$개의 줄에 걸쳐 각 질문에 대한 답을 한 줄에 하나씩 출력한다.

• $2 \leq N \leq 300\ 000$.
• $1 \leq M \leq 300\ 000$.
• $1 \leq Q \leq 300\ 000$.
• $1 \leq U_i < V_i \leq N$ ($1 \leq i \leq M$).
• $1 \leq L_i \leq R_i \leq M$ ($1 \leq i \leq Q$).