Problem Description

Xiao K likes to browse Luogu blogs to gain knowledge. Each article may have several (or possibly none) reference links pointing to other blog articles. Xiao K is eager to learn: if he reads an article, he will definitely go read the references of this article (if he has already read a reference before, then he does not need to read it again).

Assume there are a total of $n(1\le n\le10^5)$ articles in Luogu blogs (numbered from $1$ to $n$) and $m(1\le m\le10^6)$ reference-citation relations. Currently, Xiao K has opened the article numbered $1$. Please help Xiao K design a method so that he can read all the articles he can reach without repetition and without missing any.

Here is the organized reference-relation graph. In it, a reference $X\to Y$ means article $X$ has reference $Y$. It is not guaranteed that article $1$ is not cited by other articles.

Please perform DFS and BFS on this graph respectively, and output the traversal results. If there are multiple articles that can be visited, read the one with the smaller index first (so you may need to sort first).

Input Format

There are $m+1$ lines in total. The first line contains two numbers, $n$ and $m$, which indicate that there are $n(1\le n\le10^5)$ articles in total (numbered from $1$ to $n$) and $m(1\le m\le10^6)$ reference-citation relations.

In the next $m$ lines, each line contains two integers $X, Y$, meaning that article $X$ has reference $Y$.

Output Format

There are $2$ lines in total.

The first line is the DFS traversal result, and the second line is the BFS traversal result.

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 

Hint

Translated by ChatGPT 5