Description

Given a directed graph $G$ with $n$ vertices and $m$ edges, whose vertices are numbered from $1$ to $n$.

For any two vertices $u, v$, if every path from vertex $1$ to vertex $v$ must pass through vertex $u$, then vertex $u$ is said to dominate vertex $v$. In particular, every vertex dominates itself.

For any vertex $v$, the set of vertices in the graph that dominate vertex $v$ is called the dominator set of $v$, denoted by $D_v$.

Now there are $q$ independent queries. Each query gives a directed edge. You need to answer: after adding this edge to graph $G$, for how many vertices does their dominator set change.

Input Format

The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of queries, respectively.
The next $m$ lines each contain two integers $x_i, y_i$, representing a directed edge from $x_i$ to $y_i$.
The next $q$ lines each contain two integers $s_i, t_i$, representing that in this query, an edge from $s_i$ to $t_i$ is added.

The data guarantees that in the given graph $G$, all other vertices are reachable from vertex $1$, and the graph contains no multiple edges or self-loops.

Output Format

For each query, output one line with one integer, representing the answer.

6 6 3
1 2
1 3
3 4
4 5
2 6
4 1
5 6
3 2
2 4

1
0
2

见附件中的 dominator/dominator2.in。

见附件中的 dominator/dominator2.ans。

见附件中的 dominator/dominator3.in。

见附件中的 dominator/dominator3.ans。

Hint

【Sample #1 Explanation】

For the original graph, the dominator sets of the six vertices are: $D_1 = \{ 1 \}$, $D_2 = \{ 1, 2 \}$, $D_3 = \{ 1, 3 \}$, $D_4 =\{ 1, 3, 4 \}$, $D_5 = \{ 1, 3, 4, 5 \}$, $D_6 = \{ 1, 2, 6 \}$.

After adding $5 \to 6$, $D_6 = \{ 1, 6 \}$, and the dominator sets of other vertices remain unchanged.

After adding $3 \to 2$, no vertex’s dominator set changes.

After adding $2 \to 4$, $D_4 = \{ 1, 4 \}$, $D_5 = \{ 1, 4, 5 \}$, and the dominator sets of other vertices remain unchanged.

【Constraints】

For all testdata: $1 \le n \le 3 \times {10}^3$, $1 \le m \le 2 \times n$, $1 \le q \le 2 \times {10}^4$.

The detailed limits for each test point are shown in the table below:

Translated by ChatGPT 5