## 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
```