链接: https://cses.fi/problemset/task/1691

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务向一座城市的居民投递邮件。为此，你想找到一条起点和终点都是邮局的路线，并且恰好经过每条街道一次。

输入

第一行输入包含两个整数 $n$ 和 $m$：路口数量和街道数量。路口编号为 $1,2,\ldots,n$，邮局位于路口 $1$。

之后有 $m$ 行描述街道。每行包含两个整数 $a$ 和 $b$：路口 $a$ 和 $b$ 之间有一条街道。所有街道都是双向街道。

每条街道都连接两个不同的路口，且两个路口之间至多有一条街道。

输出

按你访问的顺序输出路线上的所有路口。你可以输出任意合法解。

如果没有解，输出 "IMPOSSIBLE"。

数据范围

$2 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

样例输入

6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5

样例输出

1 2 6 3 2 4 5 3 1