2013年7月30日 星期二

610 - Street Directions

根據汽車碰撞監測,很多致命的交通事故發生於雙向通行街道,為了減少意外事故的發生,市長決定要使盡可能多的街道變成單向,你被雇用來解決這個問題。

一開始給定一些雙向的道路,每個道路連接兩個十字路口,並且中間不會經過其他十字路口,每個路口最多 4 個街道相連,而最多只會有一條道路連接至相同的路口,也有可能道路的尾端是死路,當都是雙向道路時,任兩個目的地都可以相鄰。

Input 

測資有多組。

每組第一行有兩個整數 n, m (2 <= n <= 1000),接下來會有 m 行表示雙道道路的資訊,每行上有兩個整數 i j,表示路口 i 和 j 互相連接。而路口的編號為 1 到 n

n = m= 0 結束程式。

Output 

對於每組測資,先輸出測資組編號。緊接著依序輸出單向訊息 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
#



Miguel A. Revilla
1999-03-24