Researching the Ancient God Tree

Rick discovered an ancient "God Tree" within sight. The God Tree is a tree with n magical devices (nodes) and has n - 1 bidirectional magical connections. For each i (1 ≤ i ≤ n - 1), the i-th connection links devices u_i and v_i (with u_i ≠ v_i and 1 ≤ u_i, v_i ≤ n). These connections take 1 unit of time to traverse in either direction. It is guaranteed that every device is reachable from every other device using only these connections.

In addition, there are n - 1 special connections. For each device i (2 ≤ i ≤ n), there is a special connection that allows Rick to instantly teleport from device i to device 1 at no time cost. However, the special connection can be used at most once in total.

Rick starts at device 1. He wishes to research as many different magical devices as possible within a given time – researching a device only requires reaching that device, with no extra time. For every k in [1, n], determine the minimum time Rick must spend to research exactly k distinct devices and then return to device 1.

Note that Rick may choose to not use the special teleportation if it does not reduce the total time.

The magical network forms a tree. Thus, any connected set of devices containing device 1 has exactly k - 1 edges, and the normal travel cost (if Rick retraces all edges) is 2(k-1). However, by using the one special teleport from a leaf of the visited subtree (with maximum distance from device 1), Rick can save time. In particular, if the maximum distance from device 1 within the selected subtree is \(d\) (in \(\text{time}\) units), then Rick can finish the tour in \(2(k-1) - d\) time by not retracing the branch from that farthest device.

Your task is to compute, for each k (1 ≤ k ≤ n), the minimum time required. For k=1, since Rick is already at device 1, the answer is 0.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 200), the number of magical devices.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) describing a bidirectional magical connection between devices u and v.

outputFormat

Output n integers. The k-th integer denotes the minimum time required for Rick to research exactly k distinct devices and return to device 1.

Separate the numbers by spaces.

sample

1

0