测试数据来自 system/2024

描述

无向图最短路径问题，是图论中最经典也是最基础的问题之一。本题我们考虑一个有 \(n\) 个结点的无向图 \(G\)。

\(G\) 是简单完全图，也就是说 \(G\) 中没有自环，也没有重边，但任意两个不同的结点之间都有一条带权的双向边。
每一条边的边权是非负实数，但我们并不知道每一条边的具体边权。

好消息是我们知道 \(G\) 中任意两点最短路径的长度\(d(i,j)\)。且保证至少有一种边权的分配方案满足得到的带权图中\(i\)与\(j\)的最短路长度恰好是\(d(i,j)\)。

下面是留给你的任务：对于任意一对点\((i,j)\)，希望你能找出来所有合法的边权分配方案中\(i\)和\(j\)之间边权的最大值。

格式

输入格式

本题中，每一组数据都有多次询问，每一次询问分别给出了一个无向图\(G\)。

输入的第一行是一个整数 \(t\)，表示总共的询问个数。之后依次给出每一次询问。
对于每一次询问来说，第一行给出了 \(G\) 中结点总数 \(n\)。之后\(n\)行每行有\(n\)个整数，给出了一个\(n\times n\)的矩阵 \(d\)，其中第\(i\)行第\(j\)列的整数对应 \(d(i,j)\)表示\(i\)到\(j\)的最短路径长度。
因为图\(G\)是简单无向图，对角线元素\(d(i,i)\)总是\(0\)，且矩形是对称的（也就是说\(d(i,j)=d(j,i)\)）。

输出格式

对于每一次询问，若给定的图\(G\)有\(n\)个结点，则输出\(n\)行，每行有\(n\)个整数，描述了一个矩阵 \(a\)。矩阵的第\(i\)行第\(j\)列表示连接\(i\)和\(j\)的边的最大可能边权。如果\((i,j)\)的边权可以任意大，则输出字符串infty表示无限。
矩阵的对角线没有实质性意义，请全输出\(0\)。因为\(G\)是无向图，所以输出的矩阵\(a\)应该也是对称的（即\(a(i,j)=a(j,i)\)）。
不难发现，因为给定的矩阵 \(d\) 中每一个数字都是整数，所以最大可能边权总会是整数。

样例1

样例输入1

2
3
0 2 8
2 0 10
8 10 0
3
0 1 1
1 0 1
1 1 0

样例输出1

0 2 8
2 0 infty
8 infty 0
0 1 1
1 0 1
1 1 0

限制

对于 \(20\%\) 的数据，有 \(n = 3\)。

对于 \(50\%\) 的数据，有 \(1\le n\le 10\)。

对于 \(100\%\) 的数据，有 \(1\le n\le 100\)，且所有询问中\(n\)的和不超过 \(800\)，对于所有的\(d\)满足\(1\le d\le 256\)。

每一组数据的时限为 \(0.5\) 秒。