P9304 "DTOI-5" 3-1

— It seems that something called the "Sun" used to exist. The legend goes like this: white flames gave off dazzling light, and the sky was a clear, pure blue. It is said that the "Great War" started by the gods and their creations turned the land into scorched earth, and ashes covered the sky. The ashes struck the power of the stars flowing in the sky — the "Elf Corridor" — which began to glow and dyed the sky red. And that red color covered every piece of land where mutual slaughter still continued. Or perhaps it was the planet’s own wail of grief and the blood it shed... Under the blood-red sky, there was only — blue ash drifting down. ~~Come back 3579, my proudest faith/ll~~

Rick discovered an ancient "Divine Tree" within sight. The Divine Tree is a tree with $n$ positions that contain magical devices. After an initial "survey", there are $n - 1$ magical edges. The $i$-th edge $(1 \leq i \leq n - 1)$ connects two devices $u_i, v_i$, and it is guaranteed that $u_i \neq v_i$ and $1 \leq u_i, v_i \leq n$. These two devices can be traveled between **bidirectionally** in $1$ unit of time. It is guaranteed that with only these $n - 1$ edges, every device is reachable from every other device. In addition, there are $n - 1$ special edges. For each device $i \in [2, n]$, you can teleport **instantly** to device $1$ with cost $0$ time. **All special edges can be used only once in total**. Rick starts at device $1$. Now, given the structure of this "Divine Tree", Rick wants to study as many devices as possible within some amount of time. We assume that studying a device only requires arriving at that device, and costs no extra time. You need to compute as quickly as possible, for all $k \in [1, n]$, if Rick wants to study exactly $k$ different devices, **and then return to device $\bm 1$**, what is the minimum time needed.

The first line contains an integer $n$. The next $n - 1$ lines each contain two integers $u_i, v_i$.

Output $n$ lines in total. The $i$-th line contains one integer, the answer for $k = i$.

**[Sample Explanation $\bm 1$]** + When $k = 1$, Rick only needs to stay at device $1$. + When $k = 2$, Rick’s route can be $1 \rightarrow 2 \Rightarrow 1$. + When $k = 3$, Rick’s route can be $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$. + When $k = 4$, Rick’s route can be $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3 \rightarrow 1$. + When $k = 5$, Rick’s route can be $1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$. **[Sample Explanation $\bm 2$]** This testdata satisfies the properties of test points numbered $13 \sim 20$. **[Constraints and Conventions]** | Test Point ID | Special Restriction | | :--------: | :------: | | $1 \sim 2$ | $n = 3$ | | $3 \sim 4$ | $n = 5$ | | $5 \sim 6$ | $n = 100$ | | $7 \sim 8$ | $n = 1000$ | | $9 \sim 10$ | $u_i = 1, v_i = i + 1$ | | $11 \sim 12$ | $u_i = i, v_i = i + 1$ | | $13 \sim 20$ | No special restrictions | For all data, $1 \leq n \leq 10^5$, $1 \leq u_i, v_i \leq n$. Translated by ChatGPT 5