Algorithm Class - Depth-First Search 4

Interview

Time limit1sMemory limit512 MB

Summary

Run an iterative DFS from vertex R on an undirected graph, visiting neighbors in descending order, and print each vertex's depth in the DFS tree or -1 if unvisited.

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

Problem

Seojun is assisting the depth-first search (DFS) class again today. Let us check through a problem whether the students understood what his father taught in class.

An undirected graph with N vertices and M edges is given. The vertices are numbered 1 through N, and every edge has weight 1. The tree produced by a depth-first search starting at vertex R is called a depth-first search tree. Print the depth of every node in the depth-first search tree. The starting vertex R has depth 0, and an unvisited node is printed with depth -1.

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

dfs(V, E, R) {  # V : vertex set, E : edge set, R : starting vertex
    visited[R] <- YES;  # mark the starting vertex R as visited.
    for each x ∈ E(R)  # E(R) : set of vertices adjacent to vertex R. (visit vertices 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 starting 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) Every pair (u, v) of an edge is distinct.

Output

Print one integer on each of N lines, starting from the first line. The i-th line gives the depth of vertex i. The starting vertex R has depth 0, and an unvisited node is printed with depth -1.

Examples1

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