작은 장난

어느 날 밤 알은 산책을 나가기로 했다. 산책 도중 외계인은 심심해져서 장난을 치기로 했다. 도시 지도를 본 알프는 막을 도로를 하나 고른다. 그가 고르는 도로는 그 도로를 없앴을 때 집에서 명소까지의 최단 거리가 변하는 명소의 수가 가장 많은 도로이다.

도시는 정점이 $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$이고, $i \ne j$이면 $a_{i,j} > 0$이 보장된다.

문제의 답을 출력한다.