小K喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 $n(n \leq 10^5)$ 篇文章（编号为1到n）以及 $m(m \leq 10^6)$ 条参考文献引用关系。目前小K已经打开了编号为1的一篇文章，请帮助小K设计一种方法，使小K可以不重复、不遗漏的看完所有他能看到的文章。

引用关系为有向边 $X \rightarrow Y$ 表示文章X有参考文献Y，不保证编号为1的文章没有被其他文章引用。

要求：请对该图分别进行DFS和BFS遍历并输出结果，当存在多个可选的未访问文章时，优先访问编号较小的那篇。

输入描述

第一行两个正整数 $n$ 和 $m$，分别表示文章总数和引用关系总数。 接下来 $m$ 行，每行两个正整数 $u, v$，表示存在有向边 $u \rightarrow v$，即文章u的参考文献包含v。

输出描述

第一行输出DFS遍历的结果，相邻整数之间用空格分隔； 第二行输出BFS遍历的结果，相邻整数之间用空格分隔。

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