配点: 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 也是正确的。