Path Cover Matching - Repovive Standard Round 1 | Repovive

4F. Path Cover Matching

3000 pts2s256 MB

You are given a tree with $n$ vertices.

For each $k$ with $1 \le k \le n-1$ , define $f(k)$ as follows.

You choose exactly $k$ edges of the tree and mark them. Then you construct a graph $G$ on the same $n$ vertices, where you add an edge between two distinct vertices $u$ and $v$ if and only if the unique simple path between $u$ and $v$ in the tree contains at least one marked edge.

Let $\nu(G)$ be the size of a maximum matching in $G$ .
Then $f(k)$ is the maximum possible value of $\nu(G)$ over all choices of $k$ marked edges.

For each test case, output $f(1), f(2), \ldots, f(n-1)$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} f(1)\quad f(2)\quad \cdots \quad f(n-1) \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

2
1 2

Output

Case 1

1 2 2

Case 2

3 3 3 3 3

Case 3

You are given a tree with $n$ vertices.

For each $k$ with $1 \le k \le n-1$ , define $f(k)$ as follows.

Let $\nu(G)$ be the size of a maximum matching in $G$ .
Then $f(k)$ is the maximum possible value of $\nu(G)$ over all choices of $k$ marked edges.

For each test case, output $f(1), f(2), \ldots, f(n-1)$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} f(1)\quad f(2)\quad \cdots \quad f(n-1) \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

4F. Path Cover Matching

Input

Output

Samples

4F. Path Cover Matching

Constraints

Input

Output

Samples

Constraints