3-Minute Graph

Have you heard of 3-Minute Graph? It is a dish that restores the tired minds and bodies of Seoul National University Computer Science students. As the name suggests, it is quick to prepare and rich in flavor. It comes in several varieties, including Fragrant, Unscented, Complete, and Tree, so choosing one is part of the fun. Donghyeon, president of SNUPS, loves 3-Minute Graph, and his favorite is the Planar flavor.

3-Minute Graph Planar flavor. It uses domestic vertices.

The Planar flavor, as the name says, is a planar graph with $N$ vertices and $M$ edges. When you open the package, the graph is always packed in the same fixed shape. In other words, if the origin of a Euclidean coordinate system is at the lower left corner of the package, every vertex has the same coordinates each time. Edges do not cross each other except at their endpoints, and the whole graph is always connected.

Donghyeon wanted to enjoy the Planar flavor even more, and then he realized something. The name 3-Minute Graph hides a message: you should divide the graph into three parts and eat it that way.

Donghyeon plans to use this discovery to enjoy the graph at its best. He has prepared $Q$ experiments. Each experiment is a pair of distinct integers $(A,B)$ and cuts the graph into three parts with the vertical lines $x=A$ and $x=B$. A line must not pass through a vertex, because the vertex would break and he could not enjoy chewing it, so no line passes through a vertex.

A vertical line (one that does not pass through any vertex) splits the graph as follows. At every point where the line meets an edge, the edge is cut into two pieces, and a new vertex is added at each cut end.

The cut points decide how many connected components the graph splits into, meaning how many pieces the graph breaks into. Donghyeon will run each of the $Q$ experiments independently and choose the split he likes best.

Unfortunately, Donghyeon cannot afford $Q$ packages of the Planar flavor, so he asks you, a contestant at SNUPC, to run the experiments for him. Help him enjoy a delicious 3-Minute Graph!

The first line contains the number of vertices $N$, the number of edges $M$, and the number of experiments $Q$. ($2 \le N \le 100{,}000$, $1 \le M \le 200{,}000$, $1 \le Q \le 200{,}000$)

The next $N$ lines contain the coordinates $x$ and $y$ of each vertex in vertex number order. All vertex coordinates are distinct. ($1 \le x \le 10^9$, $1 \le y \le 10^9$)

The next $M$ lines contain the two vertex numbers $U$ and $V$ connected by each edge. Each edge connects two different vertices, and no two edges connect the same pair of vertices. Edges do not meet any other edge except at their endpoints. The given graph is connected. ($1 \le U \le N$, $1 \le V \le N$, $U \ne V$)

The next $Q$ lines contain two numbers $A$ and $B$, one pair per experiment. The experiment cuts the graph with the lines $x=A$ and $x=B$. Each line does not pass through a vertex, and each line crosses at least one edge. ($1 \le A < B \le 10^9$)

Print $Q$ lines. On line $i$, print the number of pieces the 3-Minute Graph splits into when the $i$-th experiment is performed. The experiments are independent of each other.