Almost Same Distance

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 ∈ 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 ≤ n ≤ 5 ⋅ 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 ≤ u_i, v_i ≤ 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 ≥ 1.

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

inputFormat

Input

The first line contains a single integer n (2 ≤ n ≤ 5 ⋅ 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 ≤ u_i, v_i ≤ n) meaning that there is an edge between vertices u_i and v_i.

It is guaranteed that the given graph is tree.

outputFormat

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 ≥ 1.

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

样例

6
1 2
1 3
1 4
4 5
4 6

4 4 2 1 1 1