Maximizing Flight Efficiency

Interview

Time limit0.5sMemory limit1024 MB

Summary

Check whether any direct flight is more expensive than a multi-stop route, and if not, count the direct flights that can be removed without changing any trip cost.

Level: Medium5 of 10
Topics: Shortest path, Matrix, Graph
Solved: No attempts yet

Problem

In the kingdom of Quadradonia, the king wants to review the prices of flights. For this purpose, he asked his accountant for a table with proposals for new prices.

However, the king studied at the Institute of Computing and Programming of Chapec´o (ICPC) and has sufficient knowledge to demand coherence in the table. The table is coherent if no multi-stop route is cheaper than a direct flight.

Once the table has been verified as coherent, the king wants to reduce the number of direct flights without increasing the cost of any trip.

Your task is to verify whether the table is coherent. If it is, find the maximum number of direct flights that can be removed without increasing the cost of any trip.

Input

The first line contains an integer $N$ ( $1 \le N \le 100$ ), the number of cities served by flights. The next $N$ lines are $L_1, L_2, \ldots, L_N$ . Line $L_i$ contains $N$ integers $C_{i1}, C_{i2}, \ldots, C_{iN}$ , where $C_{ij}$ is the cost of the direct flight between cities $i$ and $j$ .

The cost of a flight is the same in both directions, so $C_{ij} = C_{ji}$ for all $1 \le i, j \le N$ . When $i = j$ , $C_{ij} = 0$ . When $i \ne j$ , $1 \le C_{ij} \le 10^3$ .

Output

If the table is not coherent, print $-1$ . If it is coherent, print one integer on a single line: the maximum number of direct flights that can be removed without increasing the cost of any trip for passengers.

Examples3

Example 1
Input
```
3
0 1 2
1 0 1
2 1 0
```
Expected output
```
1
```
Example 2
Input
```
3
0 2 2
2 0 2
2 2 0
```
Expected output
```
0
```
Example 3
Input
```
3
0 2 9
2 0 2
9 2 0
```
Expected output
```
-1
```