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 v1 v2 ... vm [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

Added by:Bartłomiej Kowalski
Date:2006-02-09
Time limit:1s-6.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:

hide comments
2023-11-21 03:52:54 Brian Bi
It looks like, for a single test case, the maximum sum of `m` values is 5112 (i.e. 2556 undirected edges).
2013-04-17 20:24:14 wuyiqi
i think the problem should tell us how many edges of the data
2009-02-19 04:08:35 [Trichromatic] XilinX
Yes.
2009-02-18 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?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.