Collapse

There are $N$ towns along a deep linear valley in JOI Country. The towns are numbered $0, 1, \ldots, N-1$ in order of distance from the sea. Mr. I, the chair of the JOI Country Scientific Committee, maintains bidirectional communication cables between the towns. At the start, there are no cables.

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

• If $T_i = 0$, they build a cable between towns $X_i$ and $Y_i$. No cable between these two towns exists at the start of that day.
• If $T_i = 1$, they remove the cable between towns $X_i$ and $Y_i$. That cable exists at the start of that day.

Cliff collapse often happens in JOI Country. If a collapse happens between town $x$ and town $x+1$ ($0 \le x \le N-2$), every cable connecting a town numbered at most $x$ with a town numbered at least $x+1$ becomes unavailable. When a collapse happens, they choose some towns to install base stations. The base stations must be placed so that every town can reach a base station by following available cables.

Mr. I has $Q$ questions. Question $j+1$ is given by two integers $W_j$, $P_j$. It asks for the minimum number of base stations needed if a collapse happens between town $P_j$ and town $P_j+1$ at the end of day $W_j+1$.

The first line contains $N$, $C$, and $Q$. Each of the next $C$ lines contains $T_i$, $X_i$, $Y_i$. Each of the next $Q$ lines contains $W_j$ and $P_j$.

Print $Q$ lines. The $(j+1)$-th line is the answer to the $(j+1)$-th question.

Consider 5 towns. Below, $(x, y)$ denotes a cable connecting towns $x$ and $y$.

• Suppose there are 4 cables $(0, 1)$, $(1, 3)$, $(2, 4)$, and $(4, 0)$ when a collapse happens between towns 1 and 2. Cables $(1, 3)$ and $(4, 0)$ become unavailable, leaving $(0, 1)$ and $(2, 4)$. The minimum is 3, with base stations at towns 0, 2, and 3.
• Suppose there are 6 cables $(0, 1)$, $(0, 3)$, $(1, 2)$, $(2, 4)$, $(4, 0)$, and $(4, 3)$ when a collapse happens between towns 3 and 4. Cables $(2, 4)$, $(4, 0)$, and $(4, 3)$ become unavailable, leaving $(0, 1)$, $(0, 3)$, and $(1, 2)$. The minimum is 2, with base stations at towns 0 and 4.