삼분 그래프

3분 그래프라는 음식을 아는가? 3분 그래프는 서울대학교 컴퓨터공학부 학생들의 지친 심신을 위로해 주는 보양식이다. 이름에서 알 수 있듯 조리가 간편하고 풍미가 깊어서 널리 사랑받는다. 유향맛, 무향맛, 완전맛, 트리맛 등 여러 맛이 출시되어 있어서 골라 먹는 재미도 있다. SNUPS 회장 동현이도 3분 그래프를 좋아하는데, 가장 좋아하는 맛은 평면맛이다.

3분 그래프 평면맛. 국산 정점을 쓴다.

3분 그래프 평면맛은 이름에서 알 수 있듯이 정점 $N$개와 간선 $M$개로 이루어진 평면 그래프이다. 포장을 뜯으면 그 안에 항상 일정한 형태로 들어 있다. 즉, 포장지 왼쪽 아래에 유클리드 좌표계의 원점이 있다고 할 때 각 정점의 좌표는 항상 같다. 간선들은 끝점 외의 점에서 교차하지 않으며, 전체 그래프는 항상 연결되어 있다.

동현이는 평면맛을 더 맛있게 즐기려고 고민하다가 어느 날 깨달았다. 3분 그래프라는 이름에는 그래프를 세 부분으로 나누어 먹으라는 뜻이 숨어 있었다!

동현이는 이 사실을 이용해 3분 그래프를 최상의 맛으로 즐기려 한다. 이를 위해 총 $Q$개의 실험을 준비했다. 각 실험은 서로 다른 두 정수의 순서쌍 $(A,B)$로 나타내며, 직선 $x=A$와 $x=B$로 그래프를 삼분하는 실험이다. 직선이 정점을 지나면 정점이 부서져 씹는 맛을 즐길 수 없으므로, 직선은 정점을 지나지 않도록 한다.

(그래프의 정점을 지나지 않는) 수직선이 그래프를 분할한다는 것은, 수직선과 간선이 만나는 모든 지점에서 간선을 둘로 나누고, 나뉜 끝부분 각각에 새로운 정점을 추가하는 것을 뜻한다.

분할 지점에 따라 그래프의 연결 성분 수, 즉 그래프가 몇 조각으로 잘리는지가 달라진다. 동현이는 $Q$개의 실험을 각각 독립적으로 수행한 뒤, 조각이 가장 마음에 들게 나뉘는 분할 방식을 고르려 한다.

아쉽게도 동현이는 3분 그래프 평면맛을 $Q$개나 살 만큼 부자가 아니어서, SNUPC를 치르러 온 여러분에게 실험을 대신 맡기려 한다. 동현이가 맛있는 3분 그래프를 즐길 수 있도록 도와주자!

첫 번째 줄에 정점 수 $N$, 간선 수 $M$, 실험 수 $Q$가 주어진다. ($2 \le N \le 100{,}000$, $1 \le M \le 200{,}000$, $1 \le Q \le 200{,}000$)

다음 $N$개의 줄에 정점 번호 순서대로 각 정점의 좌표 $x$, $y$가 주어진다. 모든 정점의 좌표는 서로 다르다. ($1 \le x \le 10^9$, $1 \le y \le 10^9$)

다음 $M$개의 줄에 각 간선이 잇는 두 정점의 번호 $U$, $V$가 주어진다. 각 간선은 서로 다른 두 정점을 잇고, 같은 정점 쌍을 잇는 간선은 최대 하나이다. 간선은 양 끝점을 제외하고 다른 간선과 만나지 않는다. 주어지는 그래프는 연결 그래프이다. ($1 \le U \le N$, $1 \le V \le N$, $U \ne V$)

다음 $Q$개의 줄에 실험을 나타내는 두 수 $A$, $B$가 주어진다. 이는 $x=A$, $x=B$의 두 직선으로 그래프를 자른다는 뜻이다. 각 직선은 정점을 지나지 않으며, 적어도 하나의 간선을 지난다. ($1 \le A < B \le 10^9$)

$Q$개의 줄에 걸쳐, $i$번째 줄에는 $i$번째 실험을 수행했을 때 3분 그래프가 총 몇 조각으로 나뉘는지 출력한다. 실험들은 서로 독립적이다.