Breadth-First Search (BFS) - Classic Problems | Repovive

CLS11. Breadth-First Search (BFS)

1s256 MB

Given an unweighted undirected graph with $n$ vertices and $m$ edges, find the shortest distance from vertex $1$ to all other vertices.

If a vertex is unreachable from vertex $1$ , output $-1$ for that vertex.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

d_1 \quad d_2 \quad \cdots \quad d_n

d_i = \begin{cases} \text{shortest distance from } 1 \text{ to } i & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 0 1 1 2.

Output

0 1 1 2

Input

3 2
1 2
2 3

Explanation

For this input, the required output is 0 1 2.

Output

0 1 2

Input

4 2
1 2
3 4

Explanation

For this input, the required output is 0 1 -1 -1.

Output

0 1 -1 -1

1s256 MB

Given an unweighted undirected graph with $n$ vertices and $m$ edges, find the shortest distance from vertex $1$ to all other vertices.

If a vertex is unreachable from vertex $1$ , output $-1$ for that vertex.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

d_1 \quad d_2 \quad \cdots \quad d_n

d_i = \begin{cases} \text{shortest distance from } 1 \text{ to } i & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 0 1 1 2.

Output

0 1 1 2

Input

3 2
1 2
2 3

Explanation

For this input, the required output is 0 1 2.

Output

0 1 2

Input

4 2
1 2
3 4

Explanation

For this input, the required output is 0 1 -1 -1.

Output

0 1 -1 -1