Simple Shortest Path

Task

You are given an undirected graph $G$ with $N$ vertices and $M$ edges, as well as a vertex $S$. Find the length of the shortest path between $S$ and all the vertexes from the graph, including itself.

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

Input data

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

Output data

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

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq A, B \leq N$, $A \neq B$
• There are no two identical edges.
• For tests worth $40$ points, $N \leq 1 \ 000$.

Example

stdin

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

stdout

1 1 0 2 3