Distance Tree (easy version) solution codeforces

For Solution
Click Here!
This version of the problem differs from the next one only in the constraint on nn.
A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.
You are given a weighted tree with nn vertices, each edge has a weight of 11. Denote d(v)d(v) as the distance between vertex 11 and vertex vv.
Let f(x)f(x) be the minimum possible value of max1≤v≤n d(v)max1≤v≤n d(v) if you can temporarily add an edge with weight xx between any two vertices aa and bb (1≤a,b≤n)(1≤a,b≤n). Note that after this operation, the graph is no longer a tree.
For each integer xx from 11 to nn, find f(x)f(x).
The first line co ntains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The first line of each test case contains a single integer nn (2≤n≤30002≤n≤3000).
Each of the next n−1n−1 lines contains two integers uu and vv (1≤u,v≤n1≤u,v≤n) indicating that there is an edge between vertices uu and vv. It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of nn over all test cases doesn’t exceed 30003000.
For each test case, print nn integers in a single line, xxth of which is equal to f(x)f(x) for all xx from 11 to nn.
input
3 4 1 2 2 3 1 4 2 1 2 7 1 2 1 3 3 4 3 5 3 6 5 7
output Distance Tree (easy version) solution codeforces
1 2 2 2 1 1 2 2 3 3 3 3 3
 For x=1x=1, we can an edge between vertices 11 and 33, then d(1)=0d(1)=0 and d(2)=d(3)=d(4)=1d(2)=d(3)=d(4)=1, so f(1)=1f(1)=1.
 For x≥2x≥2, no matter which edge we add, d(1)=0d(1)=0, d(2)=d(4)=1d(2)=d(4)=1 and d(3)=2d(3)=2, so f(x)=2f(x)=2.

For Solution
Click Here!