362. Depth First Order

Foundation1000 ms256 MBSolved by 0%

Starting from vertex 1, print the vertices in depth-first order: follow one route as far as it goes before backing up and trying another.

When several neighbours are available, visit the SMALLER vertex number first.

Print only the vertices reachable from vertex 1.

The code is problem 361 with the queue replaced by a stack, which is the entire difference between the two traversals. There is one wrinkle: a stack returns what was pushed last, so to visit the smallest neighbour first you must push the neighbours in DESCENDING order.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.

Input

The first line contains two integers n and m, the number of vertices and edges. Each of the next m lines contains two integers u and v, an undirected edge between those vertices. Vertices are numbered 1 to n.

Output

Print the reachable vertices in depth-first order from vertex 1, separated by single spaces.

Input4 4 1 2 2 3 3 4 4 1

Output1 2 3 4

Noteis a cycle, where depth-first differs from the breadth-first answer of 1 2 4 3

Input5 4 1 2 1 3 2 4 2 5

Output1 2 4 5 3

Noteis a tree, where depth-first finishes one branch before starting the other

Input5 3 1 2 2 3 4 5

Output1 2 3

Noteis disconnected, so the far component is not visited

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution