题目描述

译自 CEOI2015 Day1 T3「Pipes」

简要题意 $\,$ 给出一个 $N$ 点 $M$ 边的无向图，不保证连通。将每个联通块视为子图，请求出每一个子图中的桥。你只有 16 MB 的内存空间。

注：原题为 16 MB，本题为了卡掉非线性空间的某算法故改为了 15 MB。

在 Cahoots 的国度里，Lomikel 是掌管管道的神。他管理水管、排水沟、下水道，甚至地铁隧道。人们在许许多多的圣泉旁敬拜他，这些圣泉由一个巨大的管道网络连接起来。每个管道直接连接两泓圣泉。

每个假期，Supreme Plumber（Lomikel 的最高祭司）会进行一场十分复杂的仪式，包括以管道运送圣水。

有时，Lomikel 的愤怒会导致管道破裂，所以 Plumber 不得不使用其他路径，使得圣水在破裂的管道周围流动。然而凡事总有不尽人意之处，对于某些管道，不存在不同的路径。这些管道被称为“关键管道”，Plumber 必须特别注意。您可以在下图中看到用粗线标出的关键管道。

你的任务是为 Plumber 找到所有关键管道。然而，网络错综复杂，而你只有非常有限的内存。空间限制仅为 16 MB。

输入格式

第一行，两个整数 $N$ 和 $M$，分别表示泉水的数量与管道的数量 $(1 \leq N \leq 100\ 000,1 \leq M \leq 6\ 000\ 000)$。

接下来 $M$ 行，每行两个整数 $u$ 和 $v$，表示有一条由 $u$ 连接 $v$ 的管道 $(1 \leq u,v \leq N)$。

两泓圣泉可以由多个管道连接，但单个管道的端点总是不同的弹簧。

技术提示：可以对标准输入进行查找（例如返回其起始位置），但查找并不是解决问题的关键。此外，若采用多次读取输入的方式效率可能会大幅下降。

输出格式

输出若干行，每行两个整数，表示一条关键管道连接的两泓圣泉。

关键管道可以以任意顺序列出，单个管道的端点也是如此。

样例

10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9

1 8
9 10

数据范围与提示

$N$ 和 $M$ 的上限如下表所示：