题目描述

小明最近正在学习图的遍历，和上次一样，他想请你帮他写一个程序，判断自己的输出对不对，输入由小明给出。 他想用深度优先搜索和广度优先搜索来解题，所以这两种正确输出都必须由你给出。 按边的输入顺序遍历。

输入格式

输入第一行有两个数n,m表示有几个点，几个边。 下面的m行，每行两个数u,v表示边（u,v）。

输出格式

共两行，第一行是广度优先搜索的结果。 第二行是深度优先搜索。

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

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

数据规模与约定

0<=n,m<=1000,1<=u,v<=n。 此乃无向图。