Problems
The shortest distance
The shortest distance
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