Description

给定一个有权图的每两个节点间的最短路径长度，判断能否找到原图。

Input

输入包括多组测试，每组测试的第一行为一个整数N，N<=100，表示图中有N个节点，然后是N行，每行有

N个整数，第i行的第j个整数k表示从i节点到j节点的最短路径距离为k，k<1000000.

Output

对于每组测试数据，如果能够找到原图，则输出构成原图所需要的最少边数，否则输出“impossible“。

Sample Input

3

0 1 1

1 0 1

1 1 0

3

0 1 3 

4 0 2

7 3 0

3

0 1 4

1 0 2

4 2 0

Sample Output

6

4

impossible

#include
      
       #include
       
        int g[102][102];int main(){    int n,i,j,k,flag,tot;    while(scanf("%d",&n)!=EOF)    {        int v[102][102];        memset(v,0,sizeof(v));        for(i=0;i