# The shortest distance

Execution time limit is 2 seconds

Runtime memory usage limit is 128 megabytes

The directed graph is given. Find the shortest distance from the vertex $x$ to other vertices of the graph.

## Input

The first line contains two integers $n$ and $x(1≤n≤1000,1≤x≤n)$ — the number of vertices in a graph and the starting vertex. Each of the next $n$ lines contains $n$ numbers — the adjacency matrix of the graph: the $i$-th line and $j$-th column contains "$1$", if the vertices $i$ and $j$ are connected with the edge, and "$0$", if there is no edge between them. The main diagonal contains zeroes.

## Output

Print the numbers $d_{1},d_{2},...,d_{n}$, where $d_{i}$ is $−1$ if there is no path from $x$ to $i$, or the minimal distance from $x$ to $i$ otherwise.

## Examples

Input #1

Answer #1

Submissions 7K

Acceptance rate 57%