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

Вхідні дані

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

Вихідні дані

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

Приклади