Dominators in a Directed Graph After Edge Addition

You are given a directed graph \( G \) with \( n \) vertices and \( m \) edges. The vertices are numbered from \( 1 \) to \( n \). In \( G \), a vertex \( u \) is said to dominate a vertex \( v \) if every path from the starting vertex \( 1 \) to \( v \) passes through \( u \). In particular, every vertex dominates itself. For each vertex \( v \), let \( D_v \) denote the set of vertices that dominate \( v \) (we call \( D_v \) the dominated set of \( v \)).

You will be given \( q \) independent queries. In each query an extra directed edge is provided. For each query, consider the graph \( G' = G \cup \{e\}\) (where \( e \) is the newly added edge) and answer how many vertices \( v \) have their dominated set \( D_v \) changed in \( G' \) compared to the original graph \( G \). Note that the queries are independent (i.e. the extra edge is not accumulated over queries).

Note: A vertex that is unreachable from vertex \( 1 \) is considered to have an empty dominated set.

inputFormat

The input begins with three integers \( n \), \( m \) and \( q \) \((1 \leq n, m, q \leq \text{some moderate bound})\).

The next \( m \) lines each contain two integers \( u \) and \( v \) indicating a directed edge from \( u \) to \( v \) in the graph \( G \).

The following \( q \) lines each contain two integers \( u \) and \( v \) representing an extra directed edge that is to be added into \( G \) for that query.

All numbers are separated by spaces or newlines.

outputFormat

For each query, output a single integer on a new line representing the number of vertices whose dominated set \( D_v \) has changed after the addition of the extra edge to \( G \).

sample

4 4 2
1 2
2 3
1 3
3 4
1 4
2 4

1
1