logo AlgoBeat OnlineJudge
登录 注册

#123. 【模板】DFS 序 / [NaOI R4T5] Flowers

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Misserina 社交名媛小娜

题目描述

万事俱备,只差一张前往 Silwave 城的车票了。米塞莉娜抵达了候车厅。

候车厅旁有一片花园。爱美的米塞莉娜怎么能够错过这样的美景呢。

花园一共有 块花田,花田间有 条道路。米塞莉娜打算从某块花田开始,以以下规则欣赏花田:

  • 如果当前花田与未去过的花田相连,那么下一次去所有未去过的花田中编号最小的那个

  • 如果当前花田没有与未去过的花田相连,那么下一次返回首次探索到这个花田前的那个花田。

例如,现在有 块花田, 有道路相连,从 号开始游览,那么米塞莉娜游览的顺序如下:

现在她已经知道花园的地图,想知道她游览花田的顺序。她最好奇的是,每一块花田第一次最后一次被游览的先后顺序,她把这个顺序称作关键游览顺序

例如上述数据顺序为:

  • 第一次游览

  • 第一次游览

  • 第一次游览

  • 最后一次游览

  • 第一次游览

  • 最后一次游览

  • 最后一次游览

  • 最后一次游览

关键游览顺序为:

她并不知道她会从哪一块开始游览,因此,你需要输出从每一块花田开始的游览顺序。

输入格式

第一行:两个整数 ,表示花田的数目和道路的数目。

接下来 行:每行两个整数 ,表示每条道路连接的花田编号。

输出格式

输出 行,第 行表示从 号花田开始的关键游览顺序

样例

样例 #1

输入 #1

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

输出 #1

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

数据范围与提示

对于 的数据:满足

对于全部测试点:满足