#1136. 「CEOI2015 Day1」管道

「CEOI2015 Day1」管道

题目描述

译自 CEOI2015 Day1 T3「Pipes

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

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


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

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

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

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

输入格式

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

接下来 MM 行,每行两个整数 uuvv,表示有一条由 uu 连接 vv 的管道 (1u,vN)(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

数据范围与提示

NNMM 的上限如下表所示:

数据点 1 2 3 4 5 6 7 8 9 10
NN\le 100100 50005000 40004000 10510^5 3×1043\times 10^4 7×1047\times 10^4 8×1048\times 10^4 10510^5
MM\le 200200 1.5×1041.5\times 10^4 6×1056\times 10^5 1.2×1061.2\times 10^6 1.5×1061.5\times 10^6 2×1062\times 10^6 3×1063\times 10^6 4×1064\times 10^6 5×1065\times 10^6 6×1066\times 10^6