给定一张 $n$ 个点 $m$ 条边的有向图 $G$，其顶点从 $1 \sim n$ 编号。

对于任意两个点 $u, v$，若从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称顶点 $u$ 支配顶点 $v$。特别地，每个顶点支配其自身。

对于任意一个点 $v$，我们将图中支配顶点 $v$ 的顶点集合称为 $v$ 的受支配集 $D_v$。

现在有 $q$ 次互相独立的询问，每次询问给出一条有向边，请你回答在图 $G$ 中加入该条边后，有多少个顶点的受支配集发生了变化。

输入格式

第一行三个整数 $n, m, q$，分别表示图中的顶点数、边数，以及询问数。

接下来 $m$ 行每行两个整数 $x_i, y_i$，表示一条有向边 $x_i \rightarrow y_i$。

接下来 $q$ 行每行两个整数 $s_i, t_i$，表示每次询问加入的边 $s_i \rightarrow t_i$。

数据保证给出的图 $G$ 中，从 $1$ 号点出发能到达所有其他点，并且图中不包含重边与自环。

输出格式

对于每个询问输出一行一个整数表示答案。

样例一

input

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

output

1
0
2

explanation

对于原图，六个点的受支配集分别为：$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\}$ 。

加入 $5 \rightarrow 6$ 后，$D_6 = \{1, 6\}$，其他点受支配集不变。

加入 $3 \rightarrow 2$ 后没有点受支配集改变。

加入 $2 \rightarrow 4 $ 后 $D_4 = \{1, 4\}, D_5 = \{1, 4, 5\}$，其他点受支配集不变。

样例二

见附加文件中 ex_dominator2.in 与 ex_dominator2.ans。

样例三

见附加文件中 ex_dominator3.in 与 ex_dominator3.ans。

限制与约定

对于所有测试数据：$1 \leq n \leq 3000, 1 \leq m \leq 2 \times n, 1 \leq q \leq 2 \times 10^4$。

每个测试点的具体限制见下表：

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载