---

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "communication.h"。

题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2 「통신망」

通信网络由 $N$ 台计算机和 $M$ 条线路组成。计算机编号从 $1$ 到 $N$。每条线路可以让两台不同的计算机进行双向通信。如果任意两台计算机可以通过一条或多条线路进行通信，则称通信网络是连通的。如果存在无法通信的计算机对，则称通信网络是断开的。

一条线路 $c$ 的风险度定义如下：

• 对于通信网络中的每台计算机 $i$，如果移除计算机 $i$ 后剩余的网络是断开的，则称计算机 $i$ 是危险的。
• 初始通信网络中移除线路 $c$ 后，危险计算机的数量即为线路 $c$ 的风险度。

请编写一个程序，计算每条线路的风险度。

实现细节

你需要实现以下函数：

vector<int> find_num_critical(int N, vector<pair<int, int>> E);

• 该函数只会被调用一次。
• 参数 $N$ 表示计算机的数量。
• 参数 $E$ 是一个大小为 $M$ 的数组，数组中的每个元素表示一条线路，由一对不同的计算机编号组成。
• 该函数返回一个长度为 $M$ 的整数数组，表示每条线路的风险度。数组中每个风险度对应的线路顺序与输入的 $E$ 相同。

注意，提交的代码中不应包含任何输入输出操作。

样例

考虑 $N=5$ 和线路 $E=[[1,5],[5,2],[2,3],[2,4],[2,5]]$ 的情况。评测程序将调用如下函数：

find_num_critical(5, [[1,5],[5,2],[2,3],[2,4],[2,5]]);

初始通信网络如下图所示：

例如，移除连接 $1$ 号和 $5$ 号计算机的线路后，通信网络如下图所示：

在这个网络中，$2$、$3$、$4$、$5$ 号计算机是危险的。注意，$1$ 号计算机移除后剩余网络仍然连通，因此不是危险的。

移除连接 $2$ 号和 $5$ 号计算机的其中一条线路后，通信网络如下图所示：

在这个网络中，$2$ 号和 $5$ 号计算机是危险的。

find_num_critical 函数应返回数组 $[4,2,4,4,2]$。

这个样例满足所有子任务的条件。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 2.5\cdot 10^5$
• $1 \leq M \leq 10^6$
• 每条线路连接两台不同的计算机
• 可能存在多条线路连接同一对计算机
• 初始通信网络是连通的

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

子任务	分值	附加限制
1	5	$N \leq 200$；$M \leq 500$
2	11	$N \leq 1000$；$M \leq 2500$
3	7	$N=M$
4	13	对于 $k \geq 2$ 台不同的计算机 $v_{1}, v_{2}, \cdots, v_{k}$ 和 $k$ 条不同的线路 $c_{1}, c_{2}, \cdots, c_{k}$，如果线路 $c_{i}$ 连接计算机 $v_{i}$ 和 $v_{i+1}$ $(1 \leq i \leq k-1)$，线路 $c_{k}$ 连接计算机 $v_{k}$ 和 $v_{1}$，则 $k$ 条线路 $c_{1}, c_{2}, \cdots, c_{k}$ 形成一个环。两个环相同意味着组成环的线路集合相同； 对于通信网络中的每条线路 $c$，包含线路 $c$ 的环最多存在一个
5	25	$N \leq 8000$；$M \leq 2.5\cdot 10^5$
6	29	$N \leq 10^5$；$M \leq 2.5\cdot 10^5$
7	10	无附加限制

示例评测程序

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$ $M$
• 第 $1+i$ $(1 \leq i \leq M)$ 行：$a_{i}$ $b_{i}$，表示 $a_{i}$ 号和 $b_{i}$ 号计算机通过线路连接

示例评测程序的输出格式如下：

• 第 $1$ 行：find_num_critical 函数返回的数组

示例评测程序可能与实际评测程序不同。

---