题目描述

题目译自 BalticOI 2020 Day2 B「Village」

在某个村庄中有 $N$ 栋房屋，每栋房屋中居住着一位村民。这些房屋由一些道路相连。每条道路连接着两栋房屋且长度恰好为 $1$ 千米。从每一栋房屋都可以通过连续的一条或若干条道路到达其他任何一个房屋。在村庄中总共有 $N-1$ 条道路。

有一天所有的村民都决定搬到不同的房屋里——也就是说，搬家完毕后每个房屋中都应该居住着一位村民，但不能有村民住在先前的房屋中。我们想知道所有村民搬家的距离总和最小和最大分别是多少。（单位：千米）

例如，如果有 $7$ 栋房屋如上图所示由道路相连，那么最小的距离总和是 $8$ 千米（这可以由以下的搬家方案实现：$1\rightarrow 6,2\rightarrow 4,3\rightarrow 1,4\rightarrow 2,5\rightarrow 7,6\rightarrow 3,7\rightarrow 5$），最大的距离总和是 $18$ 千米（这可以由以下的搬家方案实现：$1\rightarrow 7,2\rightarrow 3,3\rightarrow 4,4\rightarrow 1,5\rightarrow 2,6\rightarrow 5,7\rightarrow 6$）。

请你写一个程序，找出最小和最大的距离总和（单位：千米），并分别给村民一种分配新家的方案。

输入格式

输入第一行一个整数 $N$（$1< N\le 10^5$）。房屋用连续的整数 $1,2,\dots,n$ 编号。

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

输出格式

输出第一行两个整数，分别表示最小的搬家距离总和与最大的搬家距离总和。

第二行描述当距离总和最小时搬家的方案。共包含 $N$ 个整数 $v_1,v_2,\dots,v_N$,表示来着第 $i$ 号房子的村民应该搬到 $v_i(v_i\neq i)$。如果有多种可能的方案，输出任意一种。

第三行描述当距离总和最大时搬家的方案，格式同上。

4
1 2
2 3
3 4

4 8
2 1 4 3
4 3 2 1

7
4 2
5 7
3 4
6 3
1 3
4 5

8 18
6 4 1 2 7 3 5
7 3 4 1 2 5 6

数据范围与提示

本题共 $3$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$12$ 分）：$N\le 10$。

子任务 $2$（$38$ 分）：$N\le 1000$。

子任务 $3$（$50$ 分）：无特殊限制。

对于每组数据，若最小（或最大）值正确，并且分配方案正确，将获得 $50\%$ 的分数，但仍需保证所有输出的编号符合输出要求。