现在是 2036 年，欧洲到处都是老年人。为了让他们保持健康，欧洲多数群体部（老年人是多数！）建议让他们递送目前仍在邮寄的少量纸质邮件——这些邮件通常是寄给老年人的。这一建议即将在整个欧洲实施。

该部门设计了一个“老年邮递员系统”，具体如下：欧洲被划分为若干个邮政区域。一个邮政区域拥有一个由街道 and 交叉路口组成的街道 network。网络中的每条街道都可以双向通行。在每个区域中，可以任意雇佣多名老年人作为邮递员。每天早晨，每位邮递员都会收到一袋邮件，并按照一条覆盖部分街道网络的路线进行投递。每条路线都必须是“老年人友好型”的，即必须满足以下条件：

• 它起点和终点在同一个交叉路口。
• 它绝不经过同一个交叉路口超过一次。（以免让老年人感到困惑。）
• 它不能与其他任何路线有共同的街道；因此，区域内的每条街道都恰好由一名邮递员服务。（以免老年人之间发生争执。）

所有路线合起来必须覆盖给定的网络：网络中的每条街道都必须恰好属于一条路线。

任务

该部门现在需要一个软件，对于给定的邮政区域街道网络，计算出一组覆盖该网络的老年人友好型路线。

输入格式

输入描述了街道网络。

第一行包含两个整数 $N$ 和 $M$。$N$ 是交叉路口的数量，$M$ 是街道的数量。交叉路口从 $1$ 到 $N$ 编号。

接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le N, u \ne v$），表示有一条街道连接交叉路口 $u$ 和 $v$。

对于任何输入，均满足以下条件：

1. 任意两个交叉路口之间最多只有一条街道连接。
2. 你可以通过沿着一条或多条街道行驶，从任意一个交叉路口到达另一个交叉路口。
3. 存在解，即可以计算出一组覆盖网络的老年人友好型路线。

输出格式

输出的每一行应对应一条老年人友好型路线，并列出该路线中交叉路口的编号。交叉路口编号必须按照邮递员经过的顺序输出，起点（和终点）交叉路口最先输出（且仅输出一次）。

如果存在多个解，你的程序可以输出其中任意一个。

样例

输入格式 1

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

输出格式 1

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

说明

下图展示了街道网络以及可用于覆盖该网络的三个老年人友好型路线。

请注意，此样例有多种解，其中一些解仅包含两条路线。

子任务

• 子任务 1（38 分）：$3 \le N \le 2\,000$，$3 \le M \le 100\,000$。
• 子任务 2（17 分）：$3 \le N \le 100\,000$，$3 \le M \le 100\,000$。
• 子任务 3（45 分）：$3 \le N \le 500\,000$，$3 \le M \le 500\,000$。