← 返回题目列表

Codeforces · 118/E

E. 伯敦道路

中文机器翻译题面 查看原题

Bertown 有 n 个交叉路口和 m 条双向道路。我们知道,人们可以通过现有的道路从任何一个路口到达任何另一个路口。

随着城市里的汽车越来越多,交通拥堵开始成为现实问题。为了解决这些问题,政府决定将所有道路改为单向交通,从而缓解交通拥堵。您的任务是确定是否有一种方法可以使交通单向,以便仍然有可能从任何路口到达任何其他路口。如果答案是肯定的,您还应该找到一种可能的方法来确定道路方向。

输入

第一行包含两个空格分隔的整数n和m(2 ≤ n ≤ 105,n - 1 ≤ m ≤ 3·105),分别代表城镇中路口和道路的数量。然后跟随 m 行,每行包含两个描述城市道路的数字。每条道路由两个整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 确定—​​—它连接的路口数量。

保证沿现有双向道路从任一路口可到达任一路口。每条道路连接不同的路口,每对路口之间不超过一条道路。

输出

如果没有解决方案,则打印单个数字 0。否则,打印 m 行,每行包含两个整数 pi 和 qi — 每条道路的方向。即交通流将沿单向道路从交叉点 pi 移动到交叉点 qi。您可以按任何顺序打印道路。如果该问题有多种解决方案,请打印其中任何一个。

示例

输入 #1

6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5

输出 #1

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

输入 #2

6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4

输出 #2

0