TopCoder

User's AC Ratio

50.0% (16/32)

Submission's AC Ratio

11.7% (39/333)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10