CF1387B1.Village (Minimum)

This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth $50$ points.

There are $N$ houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly $1$ kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are $N-1$ roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

Example village with seven houses

For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is $8$ km (this can be achieved by moving $1 \to 6$, $2 \to 4$, $3 \to 1$, $4 \to 2$, $5 \to 7$, $6 \to 3$, $7 \to 5$).

Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

本题分为两个子任务。在本子任务中，你需要求出最小可能的答案；而在“村庄（最大值）”子任务中，你需要求出最大可能的答案。每个子任务各占 $50$ 分。

某村庄共有 $N$ 座房屋，每座房屋中恰好住着一位村民。房屋之间由道路相连。每条道路连接两座房屋，且长度恰好为 $1$ 千米。从任意一座房屋出发，均可经由一条或多条连续的道路到达其余任意一座房屋。整个村庄中共有 $N-1$ 条道路。

某日，所有村民决定全部搬入不同的房屋——即搬迁完成后，每座房屋仍恰好住着一位村民，但没有任何一位村民留在自己原来的房屋中。我们希望知道：所有村民从原住所到新住所的最短路径长度（单位：千米）之和的最小可能值。

含七座房屋的示例村庄

例如，若村庄中有七座房屋，其道路连接方式如图所示，则最短路径长度总和的最小值为 $8$ 千米（可通过如下搬迁方案实现：$1 \to 6$、$2 \to 4$、$3 \to 1$、$4 \to 2$、$5 \to 7$、$6 \to 3$、$7 \to 5$）。

请编写一个程序，计算最短路径长度总和（单位：千米）的最小值，并给出一个满足该最小总和的村民新住所分配方案。

The first line contains an integer $N$ ($1 \lt N \le 10^5$). Houses are numbered by consecutive integers $1, 2, \ldots, N$.

Then $N-1$ lines follow that describe the roads. Each line contains two integers $a$ and $b$ ($1 \le a, b \le N$, $a \neq b$) denoting that there is a road connecting houses $a$ and $b$.

第一行包含一个整数 $N$（$1 \lt N \le 10^5$）。房屋编号为连续的整数 $1, 2, \ldots, N$。

接下来是 $N-1$ 行，描述道路。每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le N$，$a \neq b$），表示房屋 $a$ 和 $b$ 之间有一条道路相连。

In the first line output the smallest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the smallest total length: $N$ space-separated distinct integers $v_1, v_2, \ldots, v_N$. For each $i$, $v_i$ is the house number where the villager from the house $i$ should move ($v_i \neq i$). If there are several valid assignments, output any of those.

第一行输出最短路径总长度的最小值（单位：千米）。

第二行描述一种使总长度最小的有效新住房分配方案：$N$ 个用空格分隔的互不相同的整数 $v_1, v_2, \ldots, v_N$。对每个 $i$，$v_i$ 表示原住在第 $i$ 号房屋的村民应搬迁至的房屋编号（要求 $v_i \neq i$）。若存在多种有效分配方案，输出任意一种即可。