To DFS, or to BFS, that is the question

Problem Description

TL; DR: Given a connected graph with N vertices and M bidirectional edges, please output the lexicographically smallest DFS sequence and the lexicographically smallest BFS sequence.

BB Travel Inc., a traveling agency in the ADA Kingdom, would like to launch a tourist plan that visit every city in the kingdom. The ADA Kingdom consists of N cities number from 1 to N, where the city numbered 1 is the capital. There are also M bidirectional road connecting pairs of cities. You can reach any city from any city using some of the roads.

The tourist plan should be a valid Depth-First Search (DFS) or Breadth-First Search (BFS) sequence of the kingdom starting from the capital (city 1). Thus, it should be a sequence of cities s₁,s₂,,s_N, where s₁ = 1, and each city occurs exactly once. Additionally, to attract more customers, the plan should be as attractive as possible. We say plan s is more attractive than plan s, if s is lexicographically smaller than s.

Since BB Travel Inc. doesnt know whether their customers prefer BFS order or DFS order yet, they ask you to help them find out the plan for both scenarios (i.e. one plan for DFS, and one plan for BFS).

Glossary

Please see the course slides for the definition of Depth-First Search and Breadth-First Search. Note that for the case of BFS, the order is valid as long as we choose an unvisited vertex closest to the starting vertex every time.

A valid DFS/BFS sequence is a sequence s, such that there exists a DFS/BFS search order, where s_i is the i-th vertex added into the DFS/BFS tree.

A sequence s is lexicographically smaller than s if there exists a index t, such that and s_t < s_t.

Input

The first line of the input contains two integers N and M, denoting the number of cities and the number of roads in the ADA Kingdom.

The next M lines describes the roads connecting the cities. The i-th line contains two integers u_i and v_i, denoting a bidirectional road connecting city u_i and v_i.

• 1 N 10⁵
• 1 M 2 10⁵
• 1 u_i,v_i N,1 i M
• u_i = v_i,1 i M
• You can reach any city from any city using some of the roads.
• Every pair of cities is directly connected by at most one edge.

Test Group 0 (0 %)

• Sample Input

Test Group 2 (75 %)

• No Additional Constraint Output

Test Group 1 (25 %)

• N 1000
• M 2000

Please output two lines. The first line contains the most attractive DFS trip plan starting from the capital. The second line contains the most attractive BFS trip plan starting from the capital.

Sample Input 1 Sample Input 2

5 7

5 4

5 4

1 2

3 5

• 4
• 3
• 3
• 1
• 5

1 4

• 4
• 2

Sample Output 1

Sample Output 2

1 2 5 4 3 1 4 2 3 5

1 2 4 3 5 1 4 5 2 3

Hint

1. bidirectional = undirected = unidirectional
2. Make sure you understand the sample input/outputs before coding.
3. STL is your good firend. For example:
   • You can use std::vector to store the graph (adjacency list).
   • You can use std::sort to sort an array/vector/etc.