This Holi you need to color the trees.There is a tree having N nodes with 1 as the root.A valid tree is defined as X-specific:

• Every node except the leaf node has exactly X children. Here children means immediate children.

Your task is to compute the minimum number of nodes he should remove from the tree to make the tree X-specific. Find this for all X ranging from 1 to N).

Note: You can remove the nodes which are currently leafs in a single step

Constraints

$1 \le N \le 10^5$

Input

The first line contains one integer N .

The next N−1 lines contains two integers u and v denoting that there is an edge between them.

Output

Print N lines containing the answer.