Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

F. Almost Same Distance
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $G$ be a simple graph. Let $W$ be a non-empty subset of vertices. Then $W$ is almost-$k$-uniform if for each pair of distinct vertices $u,v \in W$ the distance between $u$ and $v$ is either $k$ or $k+1$.

You are given a tree on $n$ vertices. For each $i$ between $1$ and $n$, find the maximum size of an almost-$i$-uniform set.

Input

The first line contains a single integer $n$ ($2 \leq n \leq 5 \cdot 10^5$) – the number of vertices of the tree.

Then $n-1$ lines follows, the $i$-th of which consisting of two space separated integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$) meaning that there is an edge between vertices $u_i$ and $v_i$.

It is guaranteed that the given graph is tree.

Output

Output a single line containing $n$ space separated integers $a_i$, where $a_i$ is the maximum size of an almost-$i$-uniform set.

Examples
Input
5
1 2
1 3
1 4
4 5

Output
4 3 2 1 1

Input
6
1 2
1 3
1 4
4 5
4 6

Output
4 4 2 1 1 1

Note

Consider the first example.

• The only maximum almost-$1$-uniform set is $\{1, 2, 3, 4\}$.
• One of the maximum almost-$2$-uniform sets is or $\{2, 3, 5\}$, another one is $\{2, 3, 4\}$.
• A maximum almost-$3$-uniform set is any pair of vertices on distance $3$.
• Any single vertex is an almost-$k$-uniform set for $k \geq 1$.

In the second sample there is an almost-$2$-uniform set of size $4$, and that is $\{2, 3, 5, 6\}$.