eolymp
bolt
Try our new interface for solving problems
Problems

The shortest distance

The shortest distance

Time limit 2 seconds
Memory limit 128 MiB

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

Input data

The first line contains two integers n and x~(1 \le n \le 1000, 1 \le x \le 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 data

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 example #1
6 5
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 1 1 0 0
0 1 0 0 0 0
Output example #1
2 2 1 1 0 -1