相信大家都会解决有向图的最短路问题。这次我们反着来,给你一个有向图中每一对顶点之间的最短路的长度,请你计算出原图中最少可能包含多少条边。
输入的第一行是一个整数T(T<=10),表示有T组测试数据。
每组输入的第一行是一个整数N(1<=N<=100),表示顶点个数。
接下来N行,每行输入N个整数,这些整数都小于10000。
第i行的第j个整数表示从顶点i到顶点j的最短路的长度。
第i行的第i个数字一定是0,其他的数字都大于0。
对于每组输入,先输出“Case k: ”,k表示样例的序号,从1开始。然后输出一个整数,表示原图中最少可能包含多少条边。如果原图不存在,则输出“impossible”(引号不输出)。