MDST - Minimum Diameter Spanning Tree

no tags 

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


hide comments
wuyiqi: 2013-04-17 20:24:14

i think the problem should tell us how many edges of the data

[Trichromatic] XilinX: 2009-02-19 04:08:35

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?


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