Problem Description

Mr. I has a $C$-day cable construction plan. The plan for day $(i+1)\ (0\le i\le C-1)$ is given by three integers $T_i, X_i, Y_i$, which mean:

• If $T_i=0$, they will install a cable connecting town $X_i$ and town $Y_i$. It is guaranteed that at the beginning of day $(i+1)$, there is no cable between towns $X_i$ and $Y_i$.
• If $T_i=1$, they will remove a cable connecting town $X_i$ and town $Y_i$. It is guaranteed that at the beginning of day $(i+1)$, there is a cable between towns $X_i$ and $Y_i$.

Landslides often happen in the country of JOI. If a landslide happens between towns $x$ and $x+1\ (0\le x\le N-2)$, then only cables whose two endpoints are both numbered at most $x$, or both numbered at least $x+1$, are usable. In JOI, whenever a landslide happens, they choose some towns to build base stations. The base stations must satisfy that for every town, it can be connected to a base station through some usable cables.

During the construction phase, Mr. I is already thinking about how many base stations should be built when a landslide happens. He has $Q$ questions. The $(j+1)$-th question is given by two integers $W_j, P_j$, meaning that he wants to know: after day $(W_j+1)$ ends, if a landslide happens between towns $P_j$ and $P_j+1$, what is the minimum number of base stations that should be built.

As Mr. I’s assistant, you are asked to write a program to answer Mr. I’s questions.

Input Format

On LOJ this is an interactive problem. For convenience, here it is judged in the traditional (non-interactive) way.

The first line contains three integers $N, C, Q$.

The next $C$ lines each contain three integers $T_i, X_i, Y_i$.

The next $Q$ lines each contain two integers $W_j, P_j$.

Output Format

Output $Q$ lines. The $(j+1)$-th line should output $D_j$, the answer to the $(j+1)$-th question.

5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3

3
2

Hint

Sample

Consider the case with $5$ towns. In what follows, $(x,y)$ represents a cable connecting town $x$ and town $y$.

• Suppose that when there are four cables $(0,1),(1,3),(2,4),(4,0)$, a landslide happens between towns $1$ and $2$. Cables $(1,3)$ and $(4,0)$ become unusable, so the usable cables are $(0,1)$ and $(2,4)$. You need to build base stations in towns $0,2,3$. The minimum number of base stations is $3$.
• Suppose that when there are six cables $(0, 1), (0, 3), (1, 2), (2, 4), (4, 0)$ and $(4,3)$, a landslide happens between towns $3$ and $4$. Cables $(2,4),(4,0)$ and $(4,3)$ become unusable, so the usable cables are $(0,1),(0,3)$ and $(1,2)$. You need to build base stations in towns $0$ and $4$. The minimum number of base stations is $2$.

Constraints

This problem has four subtasks. The scores and additional constraints are shown in the table below:

Translated by ChatGPT 5