P3525 [POI 2011] INS-Inspection

Byteotian Railways（BR）的铁路网络由双向轨道组成，这些轨道连接某些车站对。每对车站最多由一段轨道连接。此外，从每个车站到每个其他车站都有唯一的路线。（该路线可能由几段轨道组成，但不能经过任何车站多于一次。）Byteasar 是 BR 的一名卧底检查员。他的任务是选择一个车站（记为 $S$）作为他的行动中心，并前往所有其他车站。他的旅程应如下进行：Byteasar 从车站 $S$ 出发。接下来，他选择一个尚未检查的车站，沿最短路径（当然是乘火车）前往该车站，检查车站，然后返回 $S$。BR 的腐败员工互相警告 Byteasar 的到来。为了欺骗他们，Byteasar 选择下一个要检查的车站，使得他从车站 $S$ 出发的方向与上次不同，即沿着从 $S$ 出发的不同轨道段。每个车站（除了 $S$）恰好被检查一次。在检查完最后一个车站后，Byteasar 不返回 $S$。沿每段轨道的旅行时间相同：一小时。Byteasar 打算将所有车站都考虑为初始车站 $S$。对于每个车站，他想知道检查剩余车站的顺序，以最小化总旅行时间，前提是对于该特定 $S$ 这是可能的。

标准输入的第一行包含一个整数 $n$（$1 \le n \le 1\ 000\ 000$），表示车站的数量。这些车站从 1 到 $n$ 编号。接下来的 $n-1$ 行指定轨道段，每行一个。每行包含两个整数 $a,b$（$1 \le a,b \le n$, $a e b$），用一个空格分隔，表示有一段轨道连接车站 $a$ 和 $b$。每段轨道在描述中恰好出现一次。在至少价值 30% 的测试中，额外条件是 $n \le 2\ 000$。

你的程序应在标准输出上打印 $n$ 行，每行包含一个整数。第 $i$ 行的整数应为 Byteasar 在 $S=i$ 时检查车站所需的最少小时数——如果对于 $S=i$ 检查所有车站是可能的；如果不可能，第 $i$ 行应为数字 $-1$。

题面翻译由 ChatGPT-4o 提供。