MDST - Minimum Diameter Spanning Tree

题意翻译

# 题目描述求最小直径生成树的直径。 # 输入格式 T:T组测试数据 n:接下来有n行数据，每行第一个数是结点，第二个数m表示有m个结点与第一个数表示的结点相连。 # 输出格式每行输出一个数据，表示这个图的最小直径生成树的直径。

题目描述

Solve the minimum diameter spanning tree problem for the simple graphs. For a given list of adjacent vertices of a graph G find the minimum diameter spanning tree T and write down the diameter of this tree diam(T). Each graph has only one connected component, so there is at least one spanning tree, which connects all the vertices.

输入输出格式

输入格式

t \[the number of test graphs\] Graph: _n_ \[1 <= _n_ <= 1000 the number of graph vertices\] _i m v $ _{1} $ v $ _{2} $ ... v $ _{m} $_ \[the list of _m_ adjacent vertices to vertex _i_\]

输出格式

For each test case output: _d_ \[diameter of the minimum diameter spanning tree\]

输入输出样例

输入样例 #1

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

输出样例 #1