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