B62 - Print a Path Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

頂点数 N、辺数 M の連結なグラフが与えられます。 このグラフについて、頂点 1 から頂点 N までの単純パスを一つ出力してください。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
  • i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
  • 与えられるグラフは連結
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

次の形式で答えを 1 行に出力してください。

v_1 v_2 \cdots v_k

(v_1,v_2,\ldots,v_k) は与えられたグラフにおける頂点 1 から頂点 N への単純パスになっていなければなりません。 形式的には、(v_1,v_2,\ldots,v_k) が満たすべき条件は以下のようになります。

  • v_1=1,v_k=N
  • i\neq j\implies v_i\neq v_j
  • 与えられたグラフには辺 (v_i,v_{i+1}) が存在する (1\leq i\lt k)

入力例 1

5 4
1 2
2 3
3 4
3 5

出力例 1

1 2 3 5

与えられるグラフは次のようになります。

入力例 2

15 30
6 9
9 10
2 9
9 12
2 14
1 4
4 6
1 3
4 14
1 6
9 11
2 6
3 9
5 9
4 9
11 15
1 13
4 13
8 9
9 13
5 15
3 5
8 10
2 4
9 14
1 9
2 8
6 13
7 9
9 15

出力例 2

1 4 6 9 11 15

1 9 15 や 1 6 5 15 と出力しても正解となります。