P11915 [PA 2025] 瞬间传送 / Teleport

PA 2025 R1A.

给定一张 $n$ 个节点的简单无向连通图，边权全为 $1$。 在图中加入一条边权为 $0$ 的边，最小化**加边后**这张图的 $\displaystyle \max_{1\le u,v\le n} \{\operatorname{dist}(u,v)\}$。只需要求出 $\displaystyle \max_{1\le u,v\le n} \{\operatorname{dist}(u,v)\}$ 的最小值。 这里，$\operatorname{dist}(u,v)$ 定义为 $u,v$ 间最短路长度。

本题单个测试点内有多组测试数据。 第一行，正整数 $T$，表示测试数据组数。 接下来依次描述 $T$ 组测试数据。 每组测试数据第一行，正整数 $n$。 接下来 $n$ 行，第 $i$ 行一个长度为 $n$ 的 $\texttt{01}$ 串 $s_i$。 $s_{i,j}=1$ 表示 $(i,j)$ 存在一条边权为 $1$ 的无向边。 保证 $s_{i,j}=s_{j,i}$ 且 $s_{i,i}=\texttt{0}$。

对于每组数据输出一行一个整数，表示答案。

### 样例解释 - 样例 $1$ 解释：给定的图是完全图，无论怎么加边，最长的最短路边权总是 $1$。 - 样例 $2$ 解释：加边 $(1,5)$ 即可。 ### 数据范围 - $1\le T\le 21$； - $1\le n,\sum n\le 400$； - 给定图是简单无向连通图； - $s_{i,j}=s_{j,i}$，且 $s_{i,i}=\texttt{0}$。