MDST  Minimum Diameter Spanning Tree
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.
Input
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]
Output
For each test case output:
d [diameter of the minimum diameter spanning tree]
Example
Input: 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 Output: 5 3 0 1 2 3
hide comments
wuyiqi:
20130417 20:24:14
i think the problem should tell us how many edges of the data 

[Trichromatic] XilinX:
20090219 04:08:35
Yes. 

李同叔:
20090218 02:08:25
Can we assume that the nodes will always be in order? This means that we will never be given node 2's neighbours before node 1's. Would admin please confirm this? 
Added by:  BartÅ‚omiej Kowalski 
Date:  20060209 
Time limit:  1s6.184s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource: 