题目描述

Bessie 最近做了农场看守，他每天晚上的工作就是巡视农场并且保证没有坏人破坏农场。从谷仓出发去巡视，并且最终回到谷仓。

Bessie 视力不是很好，不能像其他农场的看守一样，对农场的每一条连接不同场地的路走一遍就可以发现是不是有异常情况，他需要每条路都走两遍，并且这两边必须是不同的方向，因为他觉得自己应该不会两次都忽略农场中的异常情况。

每块地之间一定会由至少一条路相连。现在的任务就是帮他制定巡视路线。前提假设一定存在满足题意的路径。

输入格式

第一行输入两个数N(2 <= N <= 10000)和M(1 <= M <= 50000)，表示农场一共有N块地M条路。

第二到M+1行输入两个整数，表示对应的两块地之间有一条路。

输出格式

输出2 * (m + 1)行，每行一个数字，表示Bessie 的巡查路径上地的编号，1号为谷仓，从1开始，从1结束。如果有多种你答案，输出任意一种。

样例数据

input

4 5

1 2

1 4

2 3

2 4

3 4

output

1

2

3

4

2

1

4

3

2

4

1

数据规模与约定

时间限制：$3 \text {s}$

空间限制：$65536 \text {KB}$

数据+$spj$来自2020界黄涵