36. 部落旅遊

假設總共有 N 條道路，每一條道路皆代表部落間存在道路相連接,並且設定兩部落 X 和 Z, X 代表起始點部落,Z 代表終點部落,以及給定 K 個部落作為休息點,請找出從部落 X 經過哪個休息點部落再到終點部落 Z 的路徑為最短。


【輸入說明】
第一行：輸入路徑個數N，起點部落X和終點部落Z，中間皆用一個空白隔開 (3<=N<=15, 1<=S,E<=20)
第二行：輸入K個部落作為休息點(1<=K<=5)，部落之間以一個空白隔開
第三行~第N+2行: 每一行輸入兩正整數 A B,代表 A 部落與 B 部落間有道路相連接 (1<=A,B<=20)

範例輸入說明:
5 1 3 (總共有5條路徑，起點為部落1，終點為部落3)
2 4 (休息點為部落2和部落4)
2 1 (部落2和部落1有路徑相連接)
4 5 (部落4和部落5有路徑相連接)
3 4 (部落3和部落4有路徑相連接)
2 4 (部落2和部落4有路徑相連接)
4 1 (部落4和部落1有路徑相連接)

【輸出說明】
第一行：若找不到符合條件的最短路徑，則直接輸出 NO(不用輸出第二行)，否則輸出X部落中途經過哪個休息點部落抵達 Z部落的路徑為最短。
第二行：若存在符合條件的最短路徑(從X部落到Z部落的途中有經過休息點部落)，則輸出所經過的部落，部落之間用一個空白隔開，包含起點和終點

範例輸出說明:
4 (部落1到部落3的最短路徑中，經過休息點部落4)
1 4 3 (部落1 → 部落4 → 部落 3)

【測試資料一】
輸入：
4 2 5
4
4 6
4 8
2 4
5 6

輸出：
4
2 4 6 5

【測試資料二】
輸入：
5 1 3
2 4
2 1
4 5
3 4
2 4
4 1

輸出：
4
1 4 3

【測試資料三】
輸入：
10 2 10
3 5 7 8 
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 9
8 9
9 10

輸出：
3
2 3 9 10

【測試資料四】
輸入：
8 2 9
4 6 8
1 4
4 3
5 2
3 2
1 5
6 9
8 7
6 8

輸出：
NO

【隱藏測試資料一】
輸入：
3 1 3
7
1 5
7 5
7 3

輸出：
7
1 5 7 3

【隱藏測試資料二】
輸入：
6 1 3
5 7 4
1 5
7 5
4 5
3 5
2 3
4 3

輸出：
5
1 5 3

【隱藏測試資料三】
輸入：
7 2 14
4 6 8
2 4
4 6
4 10
6 8
8 10
10 12
12 14

輸出：
4
2 4 10 12 14

【隱藏測試資料四】
輸入：
5 3 6
4 7
3 5
7 1
1 5
4 2
6 4

輸出：
NO