Найкоротша відстань

Задано орієнтовний граф. Знайдіть найкоротшу відстань від вершини $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$.

Приклади