Флойд - існування

Задано орієнтовний зважений граф. За його матрицею потрібно для кожної пари вершин визначити, чи існує найкоротший шлях між ними чи ні.

Найкоротший шлях може не існувати з двох причин:

• Немає жодного шляху.

• Є шлях як завгодно маленької ваги.

Вхідні дані

У першому рядку задається кількість вершин графа $n(1\le n\le 100)$. У наступних $n$ рядках записано по $n$ чисел, які задають зважену матрицю графа ($j$-те число у $i$-ому рядку відповідає вазі ребра з вершини $i$ у вершину $j$). В ній число $0$ означає відсутність ребра, а довільне інше число — наявність ребра відповідної ваги. Всі числа по модулю не перевищують $100$.

Вихідні дані

Виведіть $n$ рядків по $n$ чисел: $j$-те число у $i$-ому рядку повинно бути рівним $0$, якщо шлях з $i$ у $j$ не існує, $1$ — якщо існує найкоротший шлях, і $2$ — якщо існує шлях як завгодно маленької ваги.

Приклади