P7520 [NOI Qualifier Joint Contest 2021 Paper A] Dominance.

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.

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.

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

**【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: | Test Point ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | None | | $3 \sim 6$ | $100$ | $q \le 100$ | | $7 \sim 9$ | $1000$ | $m = n - 1$ | | $10 \sim 15$ | $1000$ | $q \le 2000$ | | $16 \sim 20$ | $3000$ | None | Translated by ChatGPT 5