某村庄共有 $N$ 座房屋，每座房屋里住着一名村民。这些房屋通过道路连接，每条道路连接两座房屋，长度均为 $1$ 公里。从任意一座房屋出发，都可以通过一条或多条连续的道路到达其他任何房屋。村庄中共有 $N-1$ 条道路。

有一天，所有村民决定搬到不同的房屋去住——也就是说，搬迁后每座房屋里依然住着一名村民，但没有任何一名村民住在搬迁前居住的房屋里。我们希望求出所有村民从旧居到新居的最短路径总长度的最小值和最大值（单位为公里）。

图 1：拥有七座房屋的村庄示例

例如，如果七座房屋通过如图 1 所示的道路连接，最短路径总长度的最小值为 $8$ 公里（可以通过以下搬迁方式实现：$1 \to 6, 2 \to 4, 3 \to 1, 4 \to 2, 5 \to 7, 6 \to 3, 7 \to 5$），最大值为 $18$ 公里（$1 \to 7, 2 \to 3, 3 \to 4, 4 \to 1, 5 \to 2, 6 \to 5, 7 \to 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$ 表示原先住在房屋 $i$ 的村民应搬往的房屋编号（需满足 $v_i \neq i$）。如果存在多种有效的方案，输出其中任意一种即可。

第三行应以相同的格式包含一种最短路径总长度最大的有效搬迁方案。

样例

样例输入 1

4
1 2
2 3
3 4

样例输出 1

4 8
2 1 4 3
4 3 2 1

样例输入 2

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

样例输出 2

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

子任务

1. (12 分) $N \le 10$
2. (38 分) $N \le 1000$
3. (50 分) 无额外限制

如果对于每个测试点，输出中包含正确的长度以及其中任意一种情况（最小值或最大值）的有效搬迁方案，将获得 50% 的分数。但两种情况的描述行都必须包含 $N$ 个 $1$ 到 $N$ 之间的空格分隔整数。对于（可能）不正确的那种情况，这些整数可以是该范围内的任意值（例如，全部输出为 1）。