33. Ухудшение графа

Вам дан неориентированный взвешенный граф на $n$ вершинах без кратных рёбер. От вас требуется убрать одно из рёбер графа таким образом, чтобы для максимального количества вершин расстояние от них до вершины с номером 1 изменилось.

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

В первой строке вводится число $n$ ($1 \le n \le 300$) — количество вершин в графе.

В следующих $n$ строках вводится по $n$ чисел $a_{i,j}$ через пробел ($–1 \le a_{i,j} \le 100\,000$) — элементы матрицы смежности графа. $a_{i,j}$ равно:

• 0, если i = j,
• –1, если ребро между вершинами $i, j$ отсутствует,
• $> 0$, в любом другом случае.

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

В первом тесте граф представляет из себя путь из 1 в 3 с промежуточной вершиной 2. Если удалить ребро из 1 в 2, то для вершин 2 и 3 кратчайшее расстояние от 1 до них изменится.

В третьем тесте вершина 1 изначально является изолированной, поэтому расстояние от нее до любой другой вершины не изменится с удалением ребра.