题目描述

给定 $n(n\le10^5)$ 个点（编号为 1 到 $n$）以及 $m(m\le10^6)$ 条边的有向图。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。遍历时如果遇到多个子节点，那么编号较小的节点优先(因此你可能需要先排序)。

输入格式

共 $m+1$ 行，第 1 行为 2 个数，$n$ 和 $m$。

接下来 $m$ 行，每行有两个整数 $X,Y$ 表示一条从$X$到$Y$的有向边。

输出格式

共 2 行。 第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

样例 #1

样例输入 #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