#782. 旅行

旅行

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Y\red Y 是一个爱好旅行的 OIer。她来到 X\red X 国,打算将各个城市都玩一遍。

Y\red Y 了解到,X\red X 国的 n\red{n}个城市之间有 m\red{m}条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小 Y\red Y 只能通过这些道路从一个城市前往另一个城市。

Y\red Y 的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y\red Y 回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小 Y\red Y 要求在旅行方案中,每个城市都被访问到。

为了让自己的旅行更有意义,小 Y\red Y 决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为 n\red{n}的序列。她希望这个序列的字典序最小,你能帮帮她吗?

对于两个长度均为 n\red{n}的序列 A\red{A}B\red{B},当且仅当存在一个正整数 x\red{x},满足以下条件时,我们说序列 A\red{A}的字典序小于 B\red{B}

  • 对于任意正整数 1i<x\red{1\le i\lt x},序列 A\red{A}的第 i\red{i}个元素 Ai\red{A_i}和序列 B\red{B}的第 i\red{i}个元素 Bi\red{B_i}相同。
  • 序列 A\red{A}的第 x\red{x}个元素的值小于序列 B\red{B}的第 x\red{x}个元素的值。

输入格式

输入文件共 m+1\red{m+1}行。第一行包含两个整数 n,m\red{n,m}中间用一个空格分隔。 接下来 m\red{m}行,每行包含两个整数 u,v\red{u,v},表示编号为 u\red{u}v\red{v}的城市之间有一条道路,两个整数之间用一个空格分隔。

输出格式

输出文件包含一行,n\red{n}个整数,表示字典序最小的序列。相邻两个整数之间用一个空格分隔。

样例

输入样例 1

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

输出样例 1

1 3 2 5 4 6

输入样例 2

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

输出样例 2

1 3 2 4 5 6

提示

对于全部测试数据,1n5×103\red{1\le n\le 5\times 10^3},且 m=n1\red{m=n-1}m=n\red{m=n}。保证 1u,vn\red{1\le u,v\le n}

对于不同的测试点,我们约定数据的规模如下:

测试点编号 n=\red{n=} m=\red{m=} 特殊性质
13\red{1\sim 3} 10\red{10} m=n1\red{m=n-1}
4,5\red{4,5} 100\red{100}
68\red{6\sim 8} 103\red{10^3} 每个城市最多与两个城市相连
9,10\red{9,10}
1113\red{11\sim 13} 5×103\red{5\times 10^3} 每个城市最多与三个城市相连
14,15\red{14,15}
16,17\red{16,17} 10\red{10} m=n\red{m=n}
18,19\red{18,19} 100\red{100}
2022\red{20\sim 22} 103\red{10^3} 每个城市最多与两个城市相连
2325\red{23\sim 25} 5×103\red{5\times 10^3}

提高组1

未参加
状态
已结束
规则
IOI
题目
6
开始于
2022-7-31 14:15
结束于
2022-7-31 17:15
持续时间
3 小时
主持人
参赛人数
32