비행 요금 효율 최대화

쿼드라도니아 왕국의 왕은 항공편 요금을 점검하려 한다. 이를 위해 그는 회계 담당자에게 새 요금안을 정리한 표를 요청했다.

하지만 왕은 Chapec´o 컴퓨팅 및 프로그래밍 연구소(ICPC)에서 공부한 사람이라, 표에 일관성을 요구할 만큼 지식이 충분하다. 어떤 다구간 경로도 직항보다 싸지 않으면 그 표는 일관적이다.

표가 일관적인지 확인한 뒤, 왕은 어떤 여행의 비용도 늘리지 않으면서 직항 편수를 줄이고 싶어 한다.

이 문제의 목표는 표가 일관적인지 확인하는 것이다. 일관적이라면, 어떤 여행의 비용도 늘리지 않고 없앨 수 있는 직항의 최대 개수를 구한다.

첫 줄에 항공편이 연결된 도시의 수 $N$ ($1 \le N \le 100$)이 주어진다. 이어서 $N$개의 줄 $L_1, L_2, \ldots, L_N$이 주어지며, 줄 $L_i$에는 $N$개의 정수 $C_{i1}, C_{i2}, \ldots, C_{iN}$이 있다. $C_{ij}$는 도시 $i$와 $j$ 사이 직항의 비용이다.

두 도시 사이 왕복 요금은 항상 같으므로, 모든 $1 \le i, j \le N$에 대해 $C_{ij} = C_{ji}$이다. $i = j$이면 $C_{ij} = 0$이고, $i \ne j$이면 $1 \le C_{ij} \le 10^3$이다.

표가 일관적이지 않으면 $-1$을 출력한다. 일관적이면 어떤 승객의 여행 비용도 늘리지 않고 제거할 수 있는 직항의 최대 개수를 한 줄에 출력한다.