8666: Minimum Diameter

The following is the minimum diameter problem.

• You are given a forest (an acyclic undirected graph) with $n$ vertices. Consider adding some edges to the forest to turn it into a tree. Find the minimum possible diameter of the resulting tree.

Here the diameter of a tree is defined as the maximum distance among all pairs of vertices. The distance of two vertices in a tree is defined as the number of edges on the shortest path between them.

You are given a forest of n vertices and $m$ edges. The edges are numbered from $,2,...,m$. For each $i=1,2,...,m$, consider the forest only containing the first i edges, and compute the answer to the minimum diameter problem on this forest.

The first line contains a single integer T(1≤T≤103) - the number of test cases.

For each test case, the first line contains two integers n,m(2≤n≤105,1≤m<n).

Each of next $m$ lines contains two integers u and w $(1\le u,w\le n)$ - describes the i-th edge of the forest.

It's guarantee that the sum of n among all test cases is not greater than 106 and m edges form a forest.

1
5 4
1 2
2 3
3 4
4 5

2
2
3
4