题目背景

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}$。

输出格式

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

2
4
0111
1011
1101
1110
5
01000
10100
01010
00101
00010

1
2

提示

样例解释

• 样例 $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}$。