在巴伊托奇亚（Bajtocja）的首都，每年都会举办一场盛大的自行车赛。城中有 $n$ 个地点，编号从 $1$ 到 $n$，由 $m$ 条单向道路连接。已知从地点 $1$ 可以到达任何其他地点。参赛者从某个地点 $s$ 出发，沿着道路（按其方向）行驶，最终回到出发地点 $s$（至少经过一条道路）。因此，比赛路线为 $s = t_0, t_1, t_2, \dots, t_\ell = s$（其中 $\ell \ge 1$），且对于每个 $i$（$1 \le i \le \ell$），都存在一条从地点 $t_{i-1}$ 到地点 $t_i$ 的道路。

为了增加路线的多样性，赛事组织者获得了市长的许可，可以按以下方式临时改变某些道路的方向：组织者可以选择一个由两两不同的道路组成的序列。设该序列的长度为 $k$，对于每个 $i$（$1 \le i \le k$），第 $i$ 条选定的道路必须是从地点 $z_{i-1}$ 到地点 $z_i$ 的道路。对地点 $z_i$ 没有额外限制，特别是它们不必互不相同，也不要求 $z_0 = z_k$。随后，为了比赛的需要，改变这些道路中每一条的方向，即对于每个 $i$（$1 \le i \le k$），原先从 $z_{i-1}$ 到 $z_i$ 的道路现在变为从 $z_i$ 到 $z_{i-1}$ 的道路。如果组织者选择空序列，则不进行任何改变。

现在，组织者想知道，在允许按上述方式临时改变某些道路方向的前提下，有多少个起始地点 $s$ 存在一条从 $s$ 出发并回到 $s$ 的比赛路线。我们将此数值称为“允许的起始地点数量”。

组织者从市长那里收到了一份包含 $q$ 条额外道路的列表，其中每一条道路都可以被修建以用于比赛。因此，他们希望确定对于每一条额外道路，在修建该道路后，允许的起始地点数量是多少。

你的任务是确定初始的允许起始地点数量，并确定对于 $q$ 条额外道路中的每一条，在修建该道路后允许的起始地点数量。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1\,000\,000$，$0 \le m \le 1\,000\,000$），分别表示地点数量和道路数量。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示一条从地点 $a_i$ 到地点 $b_i$ 的道路。下一行包含一个整数 $q$（$0 \le q \le 1\,000\,000$），表示额外道路的数量。接下来的 $q$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示一条从地点 $x_i$ 到地点 $y_i$ 的额外道路。

城中可能存在多条连接同一对地点的道路，也可能存在连接地点与其自身的道路。市长也可能允许在已经连接的一对地点之间修建道路。已知从地点 $1$ 可以到达任何其他地点。

输出格式

第一行应输出在不修建任何额外道路时的允许起始地点数量。接下来的 $q$ 行中，第 $i$ 行应输出修建第 $i$ 条额外道路后的允许起始地点数量。

样例

样例输入 1

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

样例输出 1

3
4
4
5

说明

样例解释：原始道路布局如下：

每个地点 $2, 3, 4$ 都是允许的起始地点。如果组织者决定改变连接地点 $2$ 和 $4$ 的道路方向，则从地点 $2, 3, 4$ 中的每一个都可以规划出一条回到自身的比赛路线。组织者也可以通过同时改变连接地点 $2$ 和 $3$ 以及 $3$ 和 $4$ 的道路方向来达到同样的目的。

在修建从地点 $1$ 到地点 $3$ 的道路后，道路布局如下：

在这种情况下，地点 $2, 3, 4$ 仍然是允许的起始地点。此外，地点 $1$ 也成为了允许的起始地点。事实上，如果组织者决定改变连接地点 $1$ 和 $3$ 的道路方向，则从地点 $1$ 可以规划出一条回到地点 $1$ 的比赛路线。

在修建从地点 $4$ 到地点 $5$ 的额外道路后，道路布局如下：

在这种情况下，地点 $2, 3, 4$ 仍然是允许的起始地点。此外，地点 $5$ 也成为了允许的起始地点。只需改变连接地点 $4$ 和 $5$ 的其中一条道路的方向即可。

最后，在修建从地点 $5$ 到地点 $1$ 的额外道路后，每个地点都将是允许的起始地点。在这种情况下，不需要改变任何道路的方向。

子任务