Necessary Roads

题目描述

有 n 个城市和 m 条道路。任意两座城市之间都有一条路径。 如果在移除某条道路后，存在两座城市之间不再有路径，则该道路称为必要道路。你的任务是找出所有必要道路。

输入格式

第一行输入包含两个整数 n 和 m：城市数和道路数。城市编号为 1,2,$\dots$,n。 接下来 m 行描述道路。每行包含两个整数 a 和 b：表示城市 a 与城市 b 之间有一条道路。任意两座城市之间最多有一条道路，且每条道路连接两个不同的城市。

输出格式

首先输出一个整数 k：必要道路的数量。随后输出 k 行，每行描述一条道路。你可以按任意顺序输出这些道路。

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

2
3 5
4 5

提示

$2 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES2076|先进技术

来源

CSES2076|先进技术