F. Флойд: существование

Дан ориентированный граф матрицей смежности, где $0$ означает отсутствие ребра, а любое другое число — вес; вес может быть отрицательным. Для каждой пары вершин определите, существует ли кратчайший путь.

Ответов три:

• $0$ — пути нет вовсе;
• $1$ — кратчайший путь существует;
• $2$ — пути есть, но их вес можно сделать сколь угодно малым.

Третий случай — отрицательный цикл. Если из $i$ можно дойти до вершины $c$, лежащей на цикле отрицательного веса, а из $c$ — до $j$, то, наматывая цикл, вес пути опускается ниже любого числа.

Первая строка содержит число $n$ ($1 \le n \le 100$).

Далее идут $n$ строк по $n$ чисел — матрица смежности. Ноль означает отсутствие ребра, любое другое число — вес. Все числа по модулю не превосходят $100$.

$n$ строк по $n$ чисел из множества $\{0, 1, 2\}$.