P15922 [TOPC 2023] Finding Bridges

无向图是图论（数学和计算机科学的一个分支）中的一个基本概念。它是一种数据结构，表示一组由无向边连接的顶点。换句话说，在无向图中，如果存在从顶点 $u$ 到顶点 $v$ 的边，则也存在从顶点 $v$ 到顶点 $u$ 的边。我们使用二元集 $\{A, B\}$ 来表示这种无向边。如果任意两个顶点之间最多只有一条边，则称该无向图为简单图。 在图论中，连通分量是指图中的一个顶点和边的集合，使得你可以通过一系列边从任意一个顶点到达任意另一个顶点。桥是无向图中的一条边，如果移除该边，会增加图中连通分量的数量。 桥是图分析中的重要概念，在网络设计、容错性和连通性分析中具有实际应用。它们通常用于识别网络中的脆弱点，即移除单条边可能导致某些组件隔离或连通性中断的位置。识别图中的桥可以通过各种算法实现，这些算法能够检测这些关键边，并帮助分析网络或系统的鲁棒性和结构。 你有一个简单无向图，其顶点和边分别为 $V = \{1, 2, \dots, n\}$ 和 $E = \{\{u_1, v_1\}, \dots, \{u_m, v_m\}\}$。你的朋友 Flora 要求你按顺序从图中移除边 $e_1, e_2, \dots, e_q$，并在每次移除后报告图中剩余的桥的数量。请编写一个程序来生成该报告。

第一行包含三个空格分隔的非负整数 $n$、$m$ 和 $q$。$n$ 是图的顶点数，$m$ 是图的边数，$q$ 是要移除的边数。接下来的 $m$ 行中，第 $i$ 行包含两个空格分隔的正整数 $u_i$ 和 $v_i$，表示 $E$ 中的第 $i$ 条边。然后是 $q$ 行，其中第 $j$ 行包含两个空格分隔的正整数 $x_j$ 和 $y_j$，表示第 $j$ 条被移除的边 $e_j = \{x_j, y_j\}$。

输出 $q$ 行。第 $k$ 行应包含一个整数 $b_k$，表示移除 $k$ 条边后图中桥的数量。

- $1 < n \le 200000$ - $1 \le m \le \min\left(200000, \binom{n}{2}\right)$ - $1 \le q \le m$ - 表示一条边 $\{u, v\}$ 有两种方式：“$u\ v$”和“$v\ u$”。 - $\{x_i, y_i\}$ 必须是 $E$ 中的一条边。 - 每条边不会被移除两次。 翻译由 DeepSeek V3.2 完成