eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кратчайшее расстояние

Кратчайшее расстояние

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа n и x~(1 \le n \le 1000, 1 \le x \le n) — количество вершин в графе и стартовая вершина соответственно. Далее в n строках по n чисел — матрица смежности графа: в i-ой строке на j-ом месте стоит "1", если вершины i и j соединены ребром, и "0", если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа d_1, d_2, ..., d_n, где d_i равно -1, если путей между x и i нет, в противном случае это минимальное рвсстояние между x и i.

Пример

Входные данные #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
Выходные данные #1
2 2 1 1 0 -1