题目背景

请用 C++14/C++17 提交以避免不必要的 CE

题目描述

村庄有 $N$ 个房子，之间有 $N-1$ 条道路连接，每条道路长度为 $1$。

在最开始，第 $i$ 个村民就在第 $i$ 号房子里，房子从 $1$ 到 $N$ 编号。

有一天，村民们突然突发奇想，想搬到别的房子中，村民们希望，在搬迁过后，不存在一位村民住在他原来居住的房子中。

求所有村民在新旧房屋之间的最小总距离值和最大总距离值。

输入格式

第一行一个整数 $N$ 代表房子数。
接下来 $N-1$ 行每行两个整数 $a,b$ 代表一条道路连接 $a$ 号房子和 $b$ 号房子。

输出格式

第一行两个整数代表所有村民在新旧房屋之间的最小总距离值和最大总距离值。
第二行 $N$ 个整数，给出一种达成最小总距离和的方案。其中第 $i$ 个整数 $v_i$ 代表第 $i$ 个村民要从 $i$ 号房子迁移到 $v_i$ 号房子。
第三行 $N$ 个整数，给出一种达成最大总距离和的方案。输出方式和上一行相同。
要保证 $v_i\ne 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

提示

评分方式

本题分为两个任务：

• 求解最小距离和，并给出一种相应的合法方案；
• 求解最大距离和，并给出一种相应的合法方案；

每成功完成一个任务，您就可以获得该测试点 $50\%$ 的分数。

您在一个子任务的得分，等于你在该子任务所有测试点的最低得分。

请注意，即使您不会求解某个子任务，也请按照要求的输出格式进行输出，否则 checker 将无法正确评分。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（12 pts）：$N \le 10$。
• Subtask 2（38 pts）：$N \le 1000$。
• Subtask 3（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le a,b \le N$。

本题使用 Special Judge。