Simple-Question

时间限制：1000ms

空间限制：256MB

背景描述

Monster很讨厌做任何和图有关的题目，所以决定考考你图的遍历。

显然Monster自己也非常菜，所以只能出一道非常简单的Simple-Question.

题目描述

给定一个图的描述，请你分别输出这个图按照深度优先遍历和广度优先遍历的结果。

当然遍历时，如果一个点连接了多个编号，按照编号的大小顺序遍历，因此你可能需要先排序。

输入格式

第一行包括$n$和$m$，表示图中将有$n$个点和$m$条边。

接下来$m$行，每行有两个数$u$和$v$，表示一条边的起点和终点。

输出格式

输出$2$行，第一行为深度优先的结果，第二行为广度优先的结果。

样例输入1

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

样例输出1

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

样例1解释

数据范围及约定

对于 $60\%$ 的数据，$1 \le n \le 10$。

对于 $100\%$ 的数据，$1 \le n \le 10^5, 1 \le m \le 10^6$。