Migrated from Lutece 738 floyd

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

已知$n$个点两两之间的最短路，求$n$个点之间最少需要连接多少条有向边才能使得两两之间的最短路满足所给方阵

Input

包含多组数据。对于每组数据，第一行包含一个数$n$（$n\le 100$），表示点的个数，接下来的$n$行每行包含$n$个非负整数，其中第$i$行第$j$个数表示第$i$个点到第$j$个点的最短路长度（$\le 10^9$）

Output

每组数据包含一行，即最少路径条数，若不存在输出$-1$

Samples

3
0 1 1
1 0 1
1 1 0
3
0 1 1
1 0 2
1 2 0

6
4

Resources

2013 UESTC ACM Training for Graph Theory