街道的方向
   

　　由Automobile Collision Monitor(ACM)的调查显示，大多数的交通事故发生在双行道上。为了减少交通事故，市长计划将尽可能多的街道改造为单行道。你被雇佣了，你的工作就是完成这个改造，使得从任一个路口仍然可以沿着某条路到达其他所有的路口。

　　你将得到城市的街道图（都是双行道），每个街道（street）连接两个路口(intersection)。两个路口之间最多只有一个街道, 最多4个街道通向一个路口。路口可能只与一个街道相连。

　　你可以假设开始可以从任一个出发路口到达任一个目的路口。

　　输入

　　输入由若干个例子组成。第一行是两个整数n和m, n为路口数(2≤n≤1000)，m为街道数。
下面m行为m个街道，每行两个整数i,j组成， 1<=i,j<=n。最后一行为n=m=0,代表输入的结束。

　　输出

　　对每个例子， 输出例子号， 随后一个空行。然后每行输出i j表示街道改造为从路口i到路口j, 对于没有改造的街道输出在不同行输出i j 和j i。最后以#结束每个例子的答案。 可能有多种解答，输出任意一种即可。

　　Sample Input

　　7 10
　　1 2
　　1 3
　　2 4
　　3 4
　　4 5
　　4 6
　　5 7
　　6 7
　　2 5
　　3 6
　　7 9
　　1 2
　　1 3
　　1 4
　　2 4
　　3 4
　　4 5
　　5 6
　　5 7
　　7 6
　　0 0

　　Sample Output

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


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有