29116번 - Маленькая шалость 다국어

Однажды ночью Аль решил пойти погулять. Во время прогулки пришельцу стало скучно, и он решил как-нибудь напакостить. А именно, увидев карту города, Альф решил перекрыть дорогу, причем не любую, а ту, после перекрытия которой кратчайшее расстояние от его дома до всех интересных мест города изменится у максимального числа интересных мест.

Город представлен в виде графа с $n$ вершинами. Дом Альфа находится в вершине с номером $1$.

Выведите максимальное число вершин, расстояние до которых изменится после удаления одного ребра в графе.

В первой строке входного файла дано число $n$ ($1 \le n \le 300$) --- количество вершин. В следующих $n$ строках дано по $n$ чисел $a_{i, j}$ ($-1 \le a_{i, j} \le 100000$) --- матрица смежности. Если ребро в графе отсутствует $a_{i, j}$ = -1. Гарантируется, что $a_{i, i}$ = 0, $a_{i, j}$ > 0 если $i$ \ne $j$.

Выведите ответ на задачу.