题目描述

本题译自 BalticOI 2014 Day2 T3「Senior Postmen」

简要题意
给一个无向连通图，请在图中找若干个简单环，要求所有简单环上的边能不重复不遗漏地覆盖整张图。

---

背景

$2036$ 年，欧洲已进入老龄化社会，此时老年人已经成为了多数群体。EMMG（the European Ministry for Majority Groups，欧洲多数群体小组）是一个保障多数群体利益的组织。为了保持老年人的健康，EMMG 建议让老年人递送已经日薄西山的纸质邮件——通常是寄给老年人的。整个欧洲即将采纳这个建议。
EMMG 设计了一套「老年邮递员制度」：

• 将欧洲划分为数个邮区，邮区是由街道和路口组成的网络。每条街道都可以双向通行。
• 在每个邮区，邮局都会雇佣若干数量的老年人当邮递员。
• 每天早上，每位邮递员都会收到一包邮件，邮递员需要按照一定的路线，把邮件派送给沿途的住户。

每一条「投递路线」都必须满足以下条件：

1. 在同一个路口出发并最终要回到这个路口。
2. 不会多次经过同一个路口（这会使老人们感到困惑）。
3. 任意两位邮递员所经过的街道互不相同（老年人之间应尽量减少摩擦）。

除此之外，所有的投递路线必须完全覆盖整个街道网络：网络中的每一条街道都必须属于某一条投递路线。

EMMG 现在需要一个这样的软件：给定一个特定的邮区的街道网络，它可以给出一组适合老人的投递路线。

---

输入格式

输入描述整个街道网络。
第一行两个正整数 $N$ 和 $M$，表示共有 $N$ 个路口，和 $M$ 条街道。路口从 $1$ 到 $N$ 编号。
接下来 $M$ 行，每行两个正整数 $u$ 和 $v$（$1 \le u, v \le N$，$u \ne v$），表示一条街道连接的两个路口。

对于任意输入，保证：

• 任意两个路口都被至多一条街道连接。
• 你可以沿着一条或多条街道从任何路口到达其他路口。
• 存在一种解决方案，即可以计算出一组覆盖整个网络的适合老人的投递路线。

---

输出格式

输出的每一行应对应一条适合老人的投递路线，并应列出该路线中的所有路口。
必须按照邮递员投递的顺序输出结点编号。
如果存在多个解决方案，您的程序可以输出其中的任何一个。

---

样例

输入：

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

输出：

2 3 4 5 8 10 9
7 8 4
1 5 7 6 3

下图说明了街道网络和三种可用于覆盖的适合老人的路线。

注意，所有解法中，某些可能只包含两条路线。

---

数据范围与提示

子任务	分值	数据范围
1	38	$3 \le N \le 2000$，$3 \le M \le 100000$
2	17	$3 \le N \le 100000$，$3 \le M \le 100000$
3	45	$3 \le N \le 500000$，$3 \le M \le 500000$