Algorithm Class - Depth-First Search 2

Interview

Time limit1sMemory limit512 MB

Summary

Given an undirected graph and a start vertex, run the supplied recursive DFS that visits neighbors in descending order, then print each vertex's visit position (0 if unreachable).

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

Problem

Seojun is once again a teaching assistant for the depth-first search (DFS) class. Let us check through a problem whether the students understood what his father taught.

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

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

dfs(V, E, R) {  # V : vertex set, E : edge set, R : start vertex
    visited[R] <- YES;  # mark that the start vertex R has been visited.
    for each x ∈ E(R)  # E(R) : set of adjacent vertices of vertex R. (visit in descending order of vertex number)
        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 start vertex R (1 ≤ R ≤ N).

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

Output

Print one integer per line over N lines, starting from the first line. The i-th line gives the visit order of vertex i. The visit order of the start vertex is 1. If a vertex cannot be reached from the start vertex, print 0.

Examples1

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