# 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*_{1}*,s*_{2}*,…,s _{N}*, where

*s*

_{1 }= 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. *doesn’t 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*, denoting a bidirectional road connecting city

_{i}*u*and

_{i }*v*.

_{i}- 1 ≤
*N*≤ 10^{5} - 1 ≤
*M*≤ 2 × 10^{5} - 1 ≤
*u*≤_{i},v_{i }*N,*∀1 ≤*i*≤*M* *u*̸=_{i }*v*∀1 ≤_{i},*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

- bidirectional = undirected ̸= unidirectional
- Make sure you understand the sample input/outputs before coding.
- 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.

## Reviews

There are no reviews yet.