T735036 【模板】割边(桥)
题目背景
给定一张无向图,图不一定连通,求出其中所有的割边(桥)。
题目描述
给定一张包含 $n$ 个点、$m$ 条边的无向图,图可能不连通。
若删除某条边后,图的连通块数量增加,则称该边为该图的一条**割边(桥)**。
请你求出图中所有的割边。
输入格式
第一行包含两个整数 $n, m$,表示图的点数和边数。
接下来 $m$ 行,每行两个整数 $u, v$,表示一条连接 $u$ 和 $v$ 的无向边。
输出格式
第一行输出一个整数 $k$,表示割边的数量。
接下来 $k$ 行,每行输出两个整数 $u\ v$,表示一条割边的两个端点。
请满足以下要求:
* 对于每条割边,输出时保证 $u < v$;
* 所有割边按 $u$ 从小到大排序;
* 若 $u$ 相同,则按 $v$ 从小到大排序。
说明/提示
### 说明
在样例中:
* 边 $3-4$ 是割边;
* 边 $4-5$ 是割边。
删除任意一条上述边后,图的连通块数量都会增加。
### 数据范围
对于 $100%$ 的数据:
* $1 \le n \le 2 \times 10^5$
* $0 \le m \le 2 \times 10^5$
* 图可能不连通
* 允许重边与自环