Traversing Citation Graph

Little K loves browsing the Luogu blog to gain knowledge. Each article may contain several (or no) reference links to other articles. Little K is extremely curious; whenever he reads an article, he will also read all the articles referenced in its bibliography (if he hasn’t read them before).

You are given a directed graph representing the citation relationships among n articles (numbered from 1 to n) and m citation relations. A citation X → Y means that article X cites article Y. Note that article 1 (the starting article) might be cited by other articles as well.

Starting from article 1, help Little K to visit all articles he can reach (without missing any and without reading any article more than once). In addition, you are required to output the order in which the articles are visited using both Depth First Search (DFS) and Breadth First Search (BFS).

When there are multiple articles available to visit, always choose the one with the smallest number first.

Note: Use the following traversal rules:

• For DFS, recursively visit the smallest numbered unvisited neighbour.
• For BFS, use a queue and enqueue available neighbours in increasing order.

The expected output is two lines: the first line is the DFS order and the second line is the BFS order, with article numbers separated by spaces.

inputFormat

The first line contains two integers n and m (n ≤ 10⁵, m ≤ 10⁶), representing the number of articles and the number of citation relations respectively.

Then m lines follow, each containing two integers u and v (1 ≤ u, v ≤ n) which indicates that article u cites article v.

outputFormat

Output two lines:

1. The first line contains the DFS traversal order starting from article 1.
2. The second line contains the BFS traversal order starting from article 1.

All article numbers in each line should be separated by a single space.

sample

4 4
1 2
1 3
2 4
3 4

1 2 4 3
1 2 3 4