|
||||||||||
Minimum DiameterTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 232 Accepted Submission(s): 61 Problem Description 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 $1,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. Input The first line contains a single integer $T$ $(1\le T\le 10^3)$ - the number of test cases. For each test case, the first line contains two integers $n,m$ $(2\le n\le 10^5,1\le 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 $10^6$ and $m$ edges form a forest. Output For each test case, output $m$ lines. The $i$-th of these lines should contain a single integer, indicating the answer to the **minimum diameter problem** on the forest only containing the first $i$ edges of the original forest. Sample Input
Sample Output
Source | ||||||||||
|