题目描述

有 $n$ 个小朋友（编号从 1 到 $n$）围成一个圆做游戏，但我们不知道他们的座位顺序。只知道其中有 $m$ 对好朋友关系，且知道所有座位相邻的小朋友都一定是好朋友。

游戏过程中好朋友之间会相互眼神交流，巧合的是，刚好他们的眼神连线都不会相交。现在给你所有好朋友关系，请构造一种可能的座位关系，按顺时针或逆时针顺序输出这个圆上的所有小朋友编号，如果有多种方案，要求输出字典序最小的一种。

简单来说，你需要输出一个字典序最小的 $1 \sim n$ 的排列，使得所有点按这个排列的顺序，在圆上顺时针分布后满足下面的条件：

• 把所有 $m$ 条边连接后（每对朋友关系都是一条边），所有边除了端点之外互不相交。

输入格式

第一行两个数 $n,m$。

接下来 $m$ 行，第 $i$ 行一组关系 $x_i,y_i$。

输出格式

一行 $n$ 个正整数，表示答案。

6 9
1 2
2 3
3 4
4 5
5 6
6 1
1 3
3 6
6 4

1 2 3 4 5 6

样例 1 解释

4 4
1 2
2 4
4 3
3 1

1 2 4 3

数据规模与约定

对于 $20\%$ 的数据，$0 \le n \le 15$。

对于 $50\%$ 的数据，$0 \le n \le 2000$。

对于 $100\%$ 的数据，$0 \le n \le 200000，$保证有解。