Algorithm Class - Depth-First Search 1

Interview

Time limit1sMemory limit512 MB

Summary

Run iterative depth-first search from vertex R on an undirected unit-weight graph, visiting neighbors in ascending order, and output each vertex's visit order or 0 if unreachable.

Level: Medium4 of 10
Topics: DFS, Graph, Stack, Sorting
Solved: No attempts yet

Problem

Seojun is once again a teaching assistant for the depth-first search (DFS) class. Check whether the students understood what his father taught by giving them this problem.

An undirected graph with N vertices and M edges is given. The vertices are numbered 1 to N, and every edge has weight 1. Starting from vertex R, visit the nodes with depth-first search and print the visit order of each node.

The pseudocode for depth-first search is as follows. Adjacent vertices are visited in ascending order.

dfs(V, E, R) {  # V : set of vertices, E : set of edges, R : starting vertex
    visited[R] <- YES;  # mark starting vertex R as visited.
    for each x ∈ E(R)  # E(R) : set of vertices adjacent to R. (visit them in ascending vertex number order)
        if (visited[x] = NO) then dfs(V, E, x);
}

Input

The first line gives the number of vertices N (5 ≤ N ≤ 100,000), the number of edges M (1 ≤ M ≤ 200,000), and the starting vertex R (1 ≤ R ≤ N).

The next M lines give edge information u v, meaning a bidirectional edge of weight 1 between vertex u and vertex v. (1 ≤ u < v ≤ N, u ≠ v) All pairs (u, v) are distinct.

Output

Print one integer per line for N lines starting from the first line. The i-th line holds the visit order of vertex i. The starting vertex has visit order 1. Print 0 for a vertex that is unreachable from the starting vertex.

Examples1

Example 1
Input
```
5 5 1
1 4
1 2
2 3
2 4
3 4
```
Expected output
```
1
2
3
4
0
```