Simple Shortest Path

Time limit: 0.5s Memory limit: 64MB Input: Output:

Task

You are given an undirected graph GG with NN vertices and MM edges, as well as a vertex SS. Find the length of the shortest path between SS and all the vertexes from the graph, including itself.

We define the shortest path between two vertices AA and BB as the smallest number of edges on a chain that connects AA and BB.

Input data

The first line will contain three numbers, NN, MM and SS, representing the number of vertices and edges the graph has, as well as the starting vertex. The next MM lines will contain the description of the graph, with one edge on each line.

Output data

The first line will contain NN numbers, representing the lengths of the shortest path between SS and every other node from the graph. If there is a node that cannot be accessed from SS, we will print 1-1 for that vertex.

Constraints and clarifications

  • 1N100 0001 \leq N \leq 100 \ 000
  • 1M200 0001 \leq M \leq 200 \ 000
  • 1A,BN1 \leq A, B \leq N, ABA \neq B
  • There are no two identical edges.
  • For tests worth 4040 points, N1 000N \leq 1 \ 000.

Example

stdin

5 5 3
1 2
1 3
1 4
2 3
5 4

stdout

1 1 0 2 3

Log in or sign up to be able to send submissions!