30074 - 最小直径生成树

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 2 秒

内存限制 : 128 MB

解决简单图的最小直径生成树问题。

对于给定的图 G 的相邻顶点列表，找到最小直径生成树 T，并写下该树的直径 diam(T)。

每个图只有一个连通分量，因此至少存在一棵生成树，连接所有顶点。

输入

第一行一个整数 $t$ ，表示测试图的数量。

对于每个测试图：

第一行一个整数 $n$ （ $1 \le n \le 1000$ ），表示图的顶点数量。
接下来 $n$ 行，第 $i$ 行表示与顶点 $i$ 相邻的顶点列表，格式为：i m v1 v2 ... vm，其中 m 表示相邻顶点数量，后面跟着 m 个相邻顶点编号。

输出

对于每个测试用例，输出一行一个整数 d，表示最小直径生成树的直径。

样例

输入

6

10
1 3 2 3 4
2 3 1 5 7
3 3 1 5 6
4 3 1 6 8
5 3 2 3 9
6 3 3 4 10
7 1 2
8 1 4
9 1 5
10 1 6

10
1 4 4 5 7 9
2 1 8
3 4 4 7 8 10
4 3 1 3 9
5 2 1 9
6 2 8 9
7 4 1 3 8 9
8 5 2 3 6 7 9
9 7 1 4 5 6 7 8 10
10 2 3 9

1
1 0

2
1 1 2
2 1 1

3
1 1 2
2 2 1 3
3 1 2

5
1 2 2 4
2 3 1 3 4
3 1 2
4 3 2 5 1
5 1 4

输出