208 - Firetruck

Center City的消防局與交通部合作，同步更新市區街道的運作情形，因為任何一天都可能因為道路維護或整修的需要而封閉部份道路，消防車需要選擇適當的路徑抵達火場，避免誤入已封閉的路段而延誤救援。

城市已被區分為不重疊的行政區，每一區都有一個消防局，當有火災警報時，火災地點所在行政區的消防局會被通報，並指示通往火災現場的所有可能的路徑。本題請你寫一個程式找出所有可能的路徑。

Input

每一個行政區的地圖都是獨立的，所有地點的編號皆為小於21的正整數，且消防局所在的地點一定是#1，每組測試資料會提供火災地點及路線圖，詳細說明如下：

• 每組測試資料的第一列有一個整數，表示火災地點的編號。
• 接下來每一列會有兩個以一到多個空白字元隔開的正整數，表示這兩個地點之間的聯絡道路是正常運作的(例如：4 7 表示4與7之間的道路是可行走的)
• 最後以兩個0表示測試資料結束。
  

Output

請對每組測試資料輸出其資料編號(CASE #1, CASE #2...)，並分別在不同列輸出每一條可行的路徑，並依序輸出路徑所經過的地點，且同一個地點不能重複經過兩次。最後一列請輸出所有路徑總數，請參考範列資料。

Sample Input

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

Sample Output

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

原文出處