In the Lemon Kingdom, there are $N$ cities and $M$ roads. The $i$-th road is a bidirectional road connecting city $U_i$ and city $V_i$. Here, $U_i < V_i$, and there may be multiple roads between two cities. However, currently, all roads are too obsolete and cannot be used.

The engineer Jaewon wants to maintain and reactivate some of these roads. However, King Damyoo XVIII of the Lemon Kingdom wants the shape of the cities to be circular. In other words, when interpreting the kingdom as an undirected graph with $N$ vertices, each connected component must satisfy one of the following conditions.

• The degree of all vertices in the component is $2$. That is, it is a simple cycle.
• The size of the component is $1$. That is, it is an isolated vertex.

Jaewon must follow Damyoo's orders, and to save costs, he plans to select and activate only consecutively numbered roads. That is, he chooses an integer pair $(l, r)$ and activates only the roads from the $l$-th road to the $r$-th road.

However, since testing all cases manually is too costly, he asked the informatics expert Woohyun for a simulation. For the $i$-th query, two integers, $L_i$ and $R_i$ are given. Woohyun needs to find the number of pairs $(l, r)$ satisfying $L_i \leq l \leq r \leq R_i$ that meet the conditions.

Become Woohyun and find the answer to each query.

The input is given in the following format.

$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$

From the first line, print the answer to each query, one per line over $Q$ lines.

• $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$).