题目描述
给你一个竞赛图，令 $\mathrm{dist}(u,v)$ 表示从 $u$ 走到 $v$ 的最短路，如果无法从 $u$ 走到 $v$ 则为 $10^9$。 求 $\min_{1\le u \le n} \max_{1\le v \le n} \mathrm{dist}(u, v)$。
输入格式
第一行是输入一个 $T$， 接下来 $T$ 组数据。 每组数据第一行一个 $n$，接下来 $n$ 行长度为 $n$ 的 01 串 $a_{i,j}$，表示是否有 $i$ 到 $j$ 的有向边。
保证 $a_{i,i} = 0, \forall i\not=j, a_{i,j}+a_{j,i} = 1$。
输出格式
输出 $T$ 行，每行一个答案。
样例输入 1
2
4
0101
0000
1101
0100
5
01100
00010
01000
10101
11100样例输出 1
1
2数据范围
保证 $1 \le n \le 10000, a_{i, j} \in \{0, 1\}$。
| 数据点编号 | $\sum n \le$ |
|---|---|
| 1, 2 | 20 |
| 3, 4 | 400 |
| 5, 6 | 1500 |
| 7, 8 | 5000 |
| 9, 10 | 10000 |
时间限制：1s
空间限制：1GB