달리기 경로

Polygonal School의 운영진은 신입생을 늘리려 하지만, 체육관이 더 많은 학생을 감당할 수 있을지 확신이 없다. 평범하고 지루한 직사각형 체육관과 달리, Polygonal의 체육관 바닥은 정$n$각형이다! 이들은 이 다각형을 애정을 담아 $P$라고 부른다.

코치는 체육관 바닥에 여러 달리기 경로를 그렸다. 각 달리기 경로는 $P$의 서로 다른 두 꼭짓점을 잇는 선분이다. 체육 시간에 코치는 학생마다 서로 다른 달리기 경로를 하나씩 배정하고, 학생은 수업이 끝날 때까지 배정받은 경로를 왕복하며 달린다. 코치는 학생들이 부딪히는 것을 원하지 않으므로, 각 학생의 경로는 다른 학생의 경로와 만나지 않아야 한다. 두 경로가 공통된 점을 하나라도 가지면(끝점도 포함) 두 경로는 만난다.

$P$에 그려진 달리기 경로가 주어질 때, 체육 시간에 동시에 달릴 수 있는 학생 수의 최댓값을 구하시오.

그림 H.1: 두 예제 입력을 나타낸 그림으로, 가능한 해답을 굵은 빨간 선으로 표시했다. 실선 검은 선은 학생에게 배정되지 않은 달리기 경로이고, 점선 검은 선은 달리기 경로가 없는 곳에서 $P$의 경계를 나타낸다.

첫째 줄에 $P$의 꼭짓점 개수 $n$이 주어진다. ($3 \le n \le 500$) 꼭짓점은 $P$를 따라 증가하는 순서로 번호가 매겨진다. 이어서 $n$개의 줄에 각각 $n$개의 정수가 주어지며, 이는 $n \times n$ 대칭 이진 행렬 $M$을 나타낸다. $i$번째 줄의 $j$번째 정수 $M_{ij}$는 다각형의 꼭짓점 $i$와 $j$ 사이에 달리기 경로가 있으면 1, 없으면 0이다. 모든 $1 \le i, j \le n$에 대해 $M_{ij} = M_{ji}$이고 $M_{ii} = 0$임이 보장된다.

위 조건에서 달리기 경로를 따라 동시에 달리도록 배정할 수 있는 학생 수의 최댓값을 출력한다.