Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

trees

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. You Are Given a Tree

time limit per test

7 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputA tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths $$$k$$$-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly $$$k$$$ vertices.

You are given a tree with $$$n$$$ vertices. For each $$$k$$$ from $$$1$$$ to $$$n$$$ inclusive find what is the maximum possible size of a $$$k$$$-valid set of simple paths.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of vertices in the tree.

Then following $$$n - 1$$$ lines describe the tree, each of them contains two integers $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree.

Output

Output $$$n$$$ numbers, the $$$i$$$-th of which is the maximum possible number of paths in an $$$i$$$-valid set of paths.

Examples

Input

7

1 2

2 3

3 4

4 5

5 6

6 7

Output

7

3

2

1

1

1

1

Input

6

1 2

2 3

2 4

1 5

5 6

Output

6

2

2

1

1

0

Note

One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 15:08:22 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|