Задание

Напишите программу, скопируйте код в поле ответа.

Ориентированный граф задан матрицей смежности. Найдите расстояния от вершины x до всех остальных вершин графа.

В первой строке входного файла содержатся два натуральных числа N и x (1⩽N⩽1000; 1⩽x⩽N) - количество вершин в графе и стартовая вершина соответственно. Далее в N строках по N чисел - матрица смежности графа: в i -й строке на j -м месте стоит «1», если вершины i и j соединены ребром, и «0», если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выведите через пробел числа d1, d2, … , dn , где di это -1, если пути из вершины x в вершину i нет, в противном случае это длина кратчайшего пути из x в i.

ввод

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

вывод

2 2 1 1 0 -1