题目背景

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 1차 선발고사 #2 통신망。

提交时，请在程序开头添加如下内容，并且无需引用 communication.h：

#include <vector>
#include <utility>

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

警告：滥用本题评测一次即可封号。

题目描述

通信网络由 $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$ 一致。

在提交的源代码的任何位置均不得调用标准输入输出操作。

输入格式

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

• 第 $1$ 行：$N \ M$
• 第 $1+i$ 行（$1 \leq i \leq M$）：$a_i \ b_i$

$a_i, b_i$ 表示 $a_i$ 号计算机与 $b_i$ 号计算机通过线路连接（$1 \leq i \leq M$）。

输出格式

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

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

请注意，示例评测程序可能与实际评测程序有所不同。

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

[4, 2, 4, 4, 2]

提示

约束条件

• $2 \leq N \leq 250\,000$
• $1 \leq M \leq 1\,000\,000$
• 每条线路连接两台不同的计算机。
• 可能存在多条线路连接同一对计算机。
• 初始网络是连通的。

子任务

1. （$5$ 分）
   • $N \leq 200$
   • $M \leq 500$
2. （$11$ 分）
   • $N \leq 1\,000$
   • $M \leq 2\,500$
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$ 构成一个环（cycle）。两个环相同当且仅当它们所包含的线路集合完全一致。
   • 在通信网络中，对于任意线路 $c$，包含 $c$ 的环最多存在一个。
5. （$25$ 分）
   • $N \leq 8\,000$
   • $M \leq 250\,000$
6. （$29$ 分）
   • $N \leq 100\,000$
   • $M \leq 250\,000$
7. （$10$ 分）
   • 无额外约束。

评分标准

只有 find_num_critical 函数返回的序列长度等于 $M$，且返回序列的所有元素与标准答案序列完全一致时，该组测试数据才会被判定为正确。

示例

• 当 $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]$。

  此示例满足所有子任务的约束。