Tree-like pasture

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka want to sell their old pasture.

The old pasture consists of \(n\) plots, numbered from \(1\) to \(n\). The pasture plots are connected by \(n-1\) paths. It is possible to get between any pair of pasture plots using the paths. In other words, the pasture has a tree-like structure.

Zenyk and Marichka will choose some plot \(w\) and a set of \(k\) plots \((w = a_1, a_2, \dots, a_k)\), where for all \(i\) from \(1\) to \(k-1\) the plots \(a_i\) and \(a_{i+1}\) are connected by a path. All \(a_i\) in the set must be distinct. Plot \(w\) is the first plot in the set. Zenyk will fence off the plots from the chosen set.

After this, the pasture will be divided into several parts, one of which will be fenced off from the others.

For all \(w\) from \(1\) to \(n\), find the maximum number of parts Zenyk and Marichka can divide the pasture into by fencing off some set of plots \((w = a_1, a_2, \dots, a_k)\).

Input

The first line contains a single integer \(n\) — the number of pasture plots.

The next \(n-1\) lines contain two integers \(u_i\) and \(v_i\) — the numbers of plots connected by paths.

Output

In a single line, print \(n\) integers — the answer to the problem for all \(w\) from \(1\) to \(n\).

Constraints

\(3 \le n \le 2 \cdot 10^5\),

\(1 \le a_i, b_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
12 1 2 1 3 1 4 5 4 6 4 4 9 9 10 11 12 4 11 6 8 6 7	8 7 7 7 6 8 7 7 7 6 7 6

Notes

The figure shows an example. For \(w=1\), it is optimal to choose the set of plots \((1, 4, 6)\) and fence off the plots from the set (marked with a blue rectangle in the figure). The pasture will be divided into eight parts, marked with different colors in the figure.