AdditionalFile5000.zip

#5000. 「POI 2023/2024 R3」Wyścig kolarski

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

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

Bajtocja 首都每年举办盛大的自行车赛。城市有 $n$ 个编号从 $1$ 到 $n$ 的地点，连接它们的 $m$ 条单向道路保证从地点 $1$ 可达任意其他地点。参赛者从某地点 $s$ 出发，沿道路方向骑行，至少经过一条道路后返回起点 $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$ 能在调整道路方向后形成从 $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 \bmod 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$。

数据范围与提示

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