「POI 2023/2024 R3」Wyścig kolarski

题目描述

题目译自 XXXI Olimpiada Informatyczna – III etap Wyścig kolarski

Bajtocja 首部每年举办盛大的自行车赛。城市有 $n$ 个编号从 $1$ 到 $n$ 的地点，连接它们的 $m$ 条单向道路保证从地点 $1$ 可达任意其他地点。参赛者从某地点出发，沿道路方向骑行，至少经过一条道路后返回起点 $s$，形成环路 $s = t_0, t_1, t_2, \ldots, t_\ell = s (\ell \geq 1)$，每对连续地点 $t_{i-1}$ 到 $t_i (1 \leq i \leq \ell)$ 存在道路。

为丰富赛道路线，组织者获市长许可，可临时调整部分道路方向：选择一个道路序列，道路两两不同，长度为 $k$，第 $i (1 \leq i \leq k)$ 条道路从 $z_{i-1}$ 到 $z_i$。地点 $z_i$ 无额外限制，可重复，且不要求 $z_0 = z_k$。随后，每条选定道路方向翻转，即从 $z_i$ 到 $z_{i-1}$。若选择空序列，则不调整。

组织者想知道，多少起点能在调整道路方向后形成从 $s$ 出发并返回的环路，称其为"可行起点数"。市长还提供了 $q$ 条可新增道路的清单，组织者需计算每条新增道路加入后可行起点数的变化。

你的任务是计算初始可行起点数，以及每条新增道路加入后的可行起点数。

输入格式

第一行包含两个整数 $n, m (1 \leq n \leq 1000000, 0 \leq m \leq 1000000)$，分别表示地点数和道路数。

接下来的 $m$ 行，每行包含两个整数 $a_i, b_i (1 \leq a_i, b_i \leq n)$，表示从 $a_i$ 到 $b_i$ 的道路。

下一行包含一个整数 $q (0 \leq q \leq 1000000)$，表示新增道路数。

接下来的 $q$ 行，每行包含两个整数 $x_i, y_i (1 \leq x_i, y_i \leq n)$，表示从 $x_i$ 到 $y_i$ 的新增道路。

城市可能有多条道路连接同一对地点，或地点到自身的道路。新增道路也可能连接已连通的地点对。从地点 $1$ 可达任意其他地点。

输出格式

第一行输出不新增道路时的可行起点数。

接下来的 $q$ 行，第 $i$ 行输出新增第 $i$ 条道路后的可行起点数。

样例

输入

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

输出

3
4
4
5

解释

初始道路网络如下：

地点 $2, 3, 4$ 为可行起点。例如，调整道路 $2 \to 4$ 的方向，或同时调整 $2 \to 3$ 和 $3 \to 4$ 的方向，可使 $2, 3, 4$ 各形成返回自身的环路。

新增道路 $1 \to 3$ 后，网络如下：

地点 $2, 3, 4$ 仍为可行起点，地点 $1$ 因调整 $1 \to 3$ 方向可形成环路，成为可行起点，总计 $4$。

新增道路 $4 \to 5$ 后，网络如下：

地点 $2, 3, 4$ 仍为可行起点，地点 $5$ 因调整 $4 \to 5$ 方向可形成环路，成为可行起点，总计 $4$。

新增道路 $5 \to 1$ 后，无需调整方向，所有地点 $1, 2, 3, 4, 5$ 均可形成环路，总计 $5$。

附加样例

1. $n = 3, m = n^2, q = 1$，每对地点间恰有一条道路，查询为 $x_1 = 2, y_1 = 2$，答案为 $3, 3$。
2. $n = 5000, m = n, q = 0, a_i = i, b_i = (i \mod n) + 1$ 对于 $1 \leq i \leq n$，答案为 $5000$。
3. $n = 500000, m = 2 \cdot (n - 1), q = 0, a_i = a_{n-1+i} = 1, b_i = b_{n-1+i} = i + 1$ 对于 $1 \leq i \leq n - 1$，答案为 $500000$。
4. $n = 1000000, m = n - 1, q = n - 3, a_i = \lfloor (i + 1)/2 \rfloor, b_i = i + 1$ 对于 $1 \leq i \leq n - 1$，查询为 $x_i = \lfloor (i + 3)/4 \rfloor, y_i = i + 3$ 对于 $1 \leq i \leq n - 3$，答案为 $0, 3, 3, \ldots, 3$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n, m, q \leq 15$	6
2	$n, m \leq 5000, q = 0$	15
3	$q = 0$	30
4	无附加限制	49