시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 1024 MB 7 5 5 71.429%

문제

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

alt text

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

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

동현이는 3분 그래프 평면맛을 더욱 맛있게 즐기기 위해 많은 고민을 해 오고 있었는데, 그러던 어느 날 갑자기 무언가를 깨달았다. 그것은 바로, 3분 그래프라는 이름에는 그래프를 세 부분으로 나누어 먹으라는 깊은 뜻이 숨겨져 있다는 사실이었다!

이제 동현이는 자신이 알아낸 엄청난 사실을 이용해 3분 그래프를 최상의 맛으로 즐기려고 한다. 이를 위해, 동현이는 총 Q개의 실험을 준비했다. 각 실험은 서로 다른 두 정수의 순서쌍 (A,B)로 나타낼 수 있으며, x=A, x=B의 두 직선으로 그래프를 삼분하는 실험을 뜻한다. 단, 직선이 정점을 지나게 될 경우 정점이 부서져 정점을 씹는 맛을 즐길 수 없기 때문에 그런 경우는 없게 할 것이다.

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

분할 지점을 어떻게 잡느냐에 따라 그래프의 연결 성분이 몇 개가 되는지, 즉 그래프가 총 몇 조각으로 잘리게 되는지가 달라질 텐데, 동현이는 Q개의 실험을 각각 독립적으로 수행한 뒤 가장 자신의 마음에 들게 조각이 나뉘는 분할 방식을 고르려고 한다.

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

입력

첫 번째 줄에 3분 그래프의 정점 수 N, 간선 수 M, 동현이가 궁금한 계획의 수 Q가 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ Q ≤ 200,000)

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

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

다음 Q개의 줄에 동현이가 준비한 실험 각각을 나타내는 두 수 A, B가 주어진다. 이는 x=A, x=B의 두 직선으로 그래프를 자른다는 뜻이다. 각 직선은 정점을 지나지 않으며, 적어도 하나의 간선을 지난다. (1 ≤ B ≤ 109)

출력

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

예제 입력 1

6 7 4
1 3
3 4
5 2
7 3
9 6
11 4
1 2
1 3
2 4
2 5
3 6
4 5
4 6
2 6
4 8
2 10
8 10

예제 출력 1

4
6
4
5