TopCoder

Thumb a

User's AC Ratio

38.9% (7/18)

Submission's AC Ratio

14.7% (23/156)

Description

給你一份地圖,地圖上標有許多城市,編號為1~n。

此外,某些城市之間有雙向的聯絡道路,現在請問從某個城市A開始,到達另一個城市B,路途中最少需要經過幾個城市呢?

你能不能把它列出來? 如果有多條路線可以經過最少的城市到達城市B,那麼我們會選擇「字典順序最小」的那條。

也就是說,如果把經過的城市依序寫出來,並且依序代表n+1進位的每一位數,那麼請輸出最小的那個數所對應的那條路線。

例如1-3-4-5與1-2-3-5,我們會優先考慮1-2-3-5。

噢對了,這個地圖上任何兩個城市之間至少有一條路線連通。

Input Format

第一列有四個正整數n, m, A, B (1<= A, B<=n,A和B相異),其中n代表有n個城市,m代表有m條聯絡道路。

接下來有m條道路的資訊:第i列有兩個數字Xi,Yi代表第i條道路來往於Xi和Yi兩個城市

Output Format

第一列請輸出從A到B所需要經過的最少城市數量。

第二列請輸出從A到B字典順序最小的最短路線。

Sample Input

範例輸入1
5 5 1 2
1 3
3 4
4 5
5 2
3 5

範例輸入2
5 5 2 5
1 2
2 3
3 4
4 5
5 1

Sample Output

範例輸出1
2
1-3-5-2

範例輸出2
1
2-1-5

Hints

佔總分30%的測試資料中,1<=n, m<=10。
佔總分60%的測試資料中,1<=n, m<=700。
對於全部的測試資料而言,1<=n, m<= 1,000,000。

Problem Source

原TIOJ1572 / 97建中校內資訊能力競賽(prob3)

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536
2 5000 65536 65536
3 5000 65536 65536
4 5000 65536 65536
5 5000 65536 65536
6 5000 65536 65536
7 5000 65536 65536
8 5000 65536 65536
9 5000 65536 65536