Description

Input

The first line of the input contains a single integer $n$ ($1\leq n\leq 5000$) — the number of vertices.

The following $n-1$ lines of the input contains $2$ integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n, u_i \neq v_i$) — indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

Output

Output $n+1$ numbers. The $i$-th number is the answer of $k=i-1$.

4
1 2
3 2
2 4

0 3 4 5 6

1

0 0

Note

Consider the first example. When $k=2$, Tenzing can paint vertices $1$ and $2$ black then the value of edge $(1,2)$ is 0, and the values of other edges are all equal to $2$. So the value of that tree is $4$.