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

For any two vertices $u, v$, if all paths from vertex $1$ to vertex $v$ must pass through vertex $u$, we say that vertex $u$ dominates vertex $v$. In particular, every vertex dominates itself.

For any vertex $v$, we call the set of vertices that dominate $v$ the dominator set of $v$, denoted by $D_v$.

There are $q$ independent queries. Each query provides a directed edge. For each query, please answer how many vertices have their dominator set changed after adding this edge to the graph $G$.

Input

The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of queries in the graph, respectively.

The next $m$ lines each contain two integers $x_i, y_i$, representing a directed edge $x_i \to y_i$.

The next $q$ lines each contain two integers $s_i, t_i$, representing the edge $s_i \to t_i$ added for each query.

It is guaranteed 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

For each query, output one integer on a new line representing the answer.

Examples

Input 1

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

Output 1

1
0
2

Note 1

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.

Examples 2

See dominator/dominator2.in and dominator/dominator2.ans in the contestant's directory.

Examples 3

See dominator/dominator3.in and dominator/dominator3.ans in the contestant's directory.

Constraints

For all test data: $1 \le n \le 3000$, $1 \le m \le 2 \times n$, $1 \le q \le 2 \times 10^4$.

The specific limits for each test case are shown in the table below: