발 디딜 곳을 조심하세요

당신은 동물원 직원으로, 최근 배설물 처리 담당에서 동물원 전체 산책로 배치를 관리하는 자리로 승진했다. 현재 모든 산책로는 일방통행이며, 동물원은 여러 구역으로 나뉘어 있다. 각 구역은 여러 볼거리(코끼리 우리, 도마뱀관 등)로 이루어져 있고, 같은 구역 안에서는 하나 이상의 산책로를 이용해 어떤 볼거리에서든 같은 구역의 다른 볼거리로 갈 수 있다. 한 구역에서 다른 구역으로 산책로를 따라 이동하면, 떠나온 구역으로는 다시 돌아올 수 없다. 그러나 동물원을 한 번 방문하는 동안 모든 구역을 걸어서 둘러볼 수는 있다. 원래 설계자들은 이러한 배치가 방문객의 흐름을 조절하는 데 매우 중요하다고 생각했다.

이사회에서 문제를 들고 당신을 찾아왔다. 이들은 구역을 나누는 방식에는 원래 설계자들과 같은 의견이지만, 일방통행 산책로를 더 추가하면 동물원이 방문객에게 좀 더 편리해질 것이라고 본다. 이들은 이전에 두 볼거리 사이에 경로가 없었던 경우에는 경로가 생기지 않도록 하면서 추가할 수 있는 산책로의 최대 개수를 구해 달라고 한다.

예를 들어, 7개의 볼거리 1("낙타 성")부터 7("하마 경마장")까지 있는 그림 J.1의 작은 동물원을 보자. 현재 볼거리 1, 2, 3, 4는 한 구역을 이루고 5, 6, 7은 다른 구역을 이룬다. 1, 2, 3, 4에서 5, 6, 7 중 어느 곳으로든 산책로를 추가할 수 있지만, (예를 들어) 7에서 1로 가는 산책로를 추가하면 방문객이 7에서 1로 갈 수 있게 되는데, 이는 이전에는 불가능했다. 한 구역 안에서 아직 없는 모든 볼거리 사이에도 산책로를 추가할 수 있다(예: 1에서 3, 2에서 4). 이 동물원에서 추가할 수 있는 산책로의 총 개수는 21이다.

그림 J.1: 예시 동물원. 이 예시는 Sample Input 1에 해당한다.

입력의 첫 줄에는 볼거리의 개수 $n$ ($1 \le n \le 2\,500$)이 주어지며, 볼거리는 1부터 $n$까지 번호가 붙는다. 그다음 $n$개의 줄이 각각 $n$개의 정수를 포함한다. $i$번째 줄의 $j$번째 정수가 1이면 볼거리 $i$에서 볼거리 $j$로 가는 일방통행 산책로가 있음을 나타내고, 그렇지 않으면 0이며 이는 그러한 산책로가 없음을 나타낸다. 볼거리에서 자기 자신으로 가는 산책로는 없다.

동물원에 추가할 수 있는 새로운 일방통행 산책로의 최대 개수를 출력한다.