問題一覧 > 通常問題

No.1190 Points

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

問題文

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

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

入力

$N\ M\ P$
$S\ G$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

入力は全て整数である
$2 \le N \le 10^5$
$1 \le M \le min(10^5,N \times (N-1)/2)$
$1 \le P \le 10^9$
$1 \le S, G \le N$
$S \neq G$
$1 \le u_i , v_i \le N$
$ u_i \neq v_i $
$ i \neq j $ の時に $ (u_i, v_i) \neq (u_j, v_j) $ かつ $ (u_i, v_i) \neq (v_j, u_j) $

出力

最初に、通る可能性のある頂点の個数 $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回通って行く方法には$(1→2→1→4),(1→3→1→4),(1→4→1→4)$の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もしくは右上の雲マークをクリックしてアカウントを作成してください。