問題一覧 > 通常問題

No.1190 Points

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 119
作問者 : AndrewKAndrewK / テスター : RhoRho
21 ProblemId : 4671 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-22 11:45:32

問題文

自己ループと二重辺を含まないN 頂点 M 辺の無向グラフが与えられます。
また、 i(1iM) 番目の辺は頂点 ui と頂点 vi を結びます。
頂点 S から頂点 G まで辺を合計でちょうど P 回通る様に移動する時、通る可能性のある頂点を全て求めなさい( S,G を含む)。

WriterでPyPy3を用いてAC出来ることを確認していますが、Python3でAC出来るかは未確認です。
Pythonでの提出には十分ご注意ください。

入力

N M P
S G
u1 v1
u2 v2

uM vM

入力は全て整数である
2N105
1Mmin(105,N×(N1)/2)
1P109
1S,GN
SG
1ui,viN
uivi
ij の時に (ui,vi)(uj,vj) かつ (ui,vi)(vj,uj)

出力

最初に、通る可能性のある頂点の個数 K を出力し、続く K 行に昇順に通る可能性のある頂点を出力しなさい。
ただし、条件を満たす移動をすることができない場合は1と出力しなさい。
最後に改行してください。

サンプル

サンプル1
入力
6 5 3
1 4
1 2
1 3
1 4
2 5
3 6
出力
4
1
2
3
4

点1から点4まで辺を3回通って行く方法には(1214),(1314),(1414)の3通りがあります。

サンプル2
入力
4 3 4
1 4
1 2
2 3
3 4
出力
-1

サンプル3
入力
10 9 5
1 10
7 2
4 9
5 3
1 9
2 9
8 7
8 5
6 4
10 2
出力
6
1
2
4
7
9
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。