题目描述

这是一个有向强连通图，输入顶点数n，弧数m，输入m条弧的信息，包括：起始顶点编号，到达顶点编号，顶点编号为1~n。

题目保证输入弧顺序为：按起始顶点编号升序排列，对于起始顶点相同的弧，按到达顶点编号升序排列。

从顶点1开始进行深度优先遍历，输出顶点序列。

从顶点1开始进行广度优先遍历，输出顶点序列。

输入格式

第一行：输入顶点数n，弧数m (2≤n≤30, 1≤m≤200)

以下m行：每行两个整数a,b，表示存在一条从顶点a到顶点b的弧

输出格式

第一行：从顶点1开始进行深度优先遍历得到的顶点序列

第二行：从顶点1开始进行广度优先遍历得到的顶点序列

4 3
1 2
1 4
2 3

1 2 3 4
1 2 4 3