Problem Description

Given a directed graph \( G \) with \( n \) vertices and \( m \) edges, where the vertices are numbered from 1 to \( n \).

For any two vertices \( u \) and \( v \), if all paths from vertex 1 to vertex \( v \) must pass through vertex \( u \), then vertex \( u \) is said to dominate vertex \( v \). Notably, each vertex dominates itself.

For any vertex \( v \), the set of vertices that dominate \( v \) is called the dominated set \( D_v \) of \( v \).

There are \( q \) independent queries. Each query provides a directed edge, and you are asked to determine how many vertices have their dominated sets changed after adding this edge to the graph \( G \).

Input Format

The first line contains three integers \( n \), \( m \), and \( 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 \) and \( y_i \), indicating a directed edge from \( x_i \) to \( y_i \).

The following \( q \) lines each contain two integers \( s_i \) and \( t_i \), representing the edge to be added in each query from \( s_i \) to \( t_i \).

The input guarantees that the graph \( G \) can be reached from vertex 1 to all other vertices, and the graph does not contain duplicate edges or self-loops.

Output Format

For each query, output one line containing a single integer, which is the answer to the query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
0
2

Input Sample #2

See the attached file dominator/dominator2.in.

Output Sample #2

See the attached file dominator/dominator2.ans.

Input Sample #3

See the attached file dominator/dominator3.in.

Output Sample #3

See the attached file dominator/dominator3.ans.

Notes

[Sample #1 Explanation]

For the original graph, the dominated 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 the edge \( 5 \to 6 \), \( D_6 = \{ 1, 6 \} \), and the dominated sets of other vertices remain unchanged.

After adding the edge \( 3 \to 2 \), no vertices' dominated sets change.

After adding the edge \( 2 \to 4 \), \( D_4 = \{ 1, 4 \} \), \( D_5 = \{ 1, 4, 5 \} \), and the dominated sets of other vertices remain unchanged.

[Data Range]

For all test data: \( 1 \le n \le 3 \times 10^3 \), \( 1 \le m \le 2 \times n \), \( 1 \le q \le 2 \times 10^4 \).

Specific restrictions for each test point are as follows:

见题面 Input 部分

见题面 Output 部分