题目描述

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

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

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

• 将欧洲划分为数个邮区，邮区是由街道和路口组成的网络。每条街道都可以双向通行。
• 在每个邮区，邮局都会雇佣若干数量的老年人当邮递员。
• 每天早上，每位邮递员都会收到一包邮件，邮递员需要按照一定的路线，把邮件派送给沿途的住户。
• 每一条「投递路线」都必须满足以下条件：
  • 在同一个路口出发并最终要回到这个路口。
  • 不会多次经过同一个路口（这会使老人们感到困惑）。
  • 任意两位邮递员所经过的街道互不相同（老年人之间应尽量减少摩擦）。
• 除此之外，所有的投递路线必须完全覆盖整个街道网络：网络中的每一条街道都必须属于某一条投递路线。

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

输入格式

输入描述整个街道网络。
第一行两个正整数，$N$ 和 $M$，表示共有 $N$ 个路口，和 $M$ 条街道。路口从 $1$ 到 $N$ 编号。
接下来 $M$ 行，每行两个正整数 $u$ 和 $v$ $(1 ≤ u, v ≤ N, u \ne v)$，表示一条街道连接的两个路口。
对于任意输入，保证：

1. 任意两个路口都被至多一条街道连接。

2. 你可以沿着一条或多条街道从任何路口到达其他路口。

3. 存在一种解决方案，即可以计算出一组覆盖整个网络的适合老人的投递路线。

输出格式

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

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

数据范围与提示