题目描述

小周喜欢在知识网站上翻看文章。每篇文章末尾可能有若干条（也可能没有）「延伸阅读」链接，指向别的文章。小周求知欲很强：只要他读了某篇文章，就一定会去读它延伸阅读的每一篇（如果之前已经读过那篇，就不必再读了）。

假设网站里一共有 $n(1\le n\le10^5)$ 篇文章（编号为 $1$ 到 $n$）以及 $m(1\le m\le10^6)$ 条延伸阅读关系。目前小周已经打开了编号为 $1$ 的文章，请帮小周设计一种顺序，使他不重复、不遗漏地读完所有他能读到的文章。

关系 $X\to Y$ 表示文章 $X$ 的延伸阅读里有文章 $Y$。不保证编号为 $1$ 的文章没有被其他文章引用。

请对这些关系分别进行 DFS 和 BFS，并输出遍历结果。如果同时有很多篇文章可以读，请先读编号较小的那篇（因此你可能需要先排序）。

输入格式

共 $m+1$ 行，第 $1$ 行为 $2$ 个数 $n$ 和 $m$，分别表示一共有 $n(1\le n\le10^5)$ 篇文章（编号为 $1$ 到 $n$）以及 $m(1\le m\le10^6)$ 条延伸阅读关系。

接下来 $m$ 行，每行有两个整数 $X,Y$，表示文章 $X$ 的延伸阅读里有文章 $Y$。

输出格式

共 $2$ 行。

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

样例

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

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