题目描述

这棵树一共有 $n$ 个节点，编号为 $1\sim n$。小方有 $n$ 个小球，编号也为 $1\sim n$。他要将这 $n$ 个小球放到树上的每个节点上，每个节点放一个球，$i$ 号球放的节点为 $p_i$。

放完之后，小方要做如下 $n$ 次操作：第 $i$ 次操作找到编号为 $i$ 的球，并将其与节点 $i$ 上的球交换，这次操作代价为这两个球在树上的距离。定义总代价为 $n$ 次操作代价总和。

显然 $n$ 次操作完 $i$ 号球在节点 $i$ 上，且总代价只由初始每个节点放的球有关。

小方想要最大化总代价，在此基础上最小化序列 $p_1,p_2,\dots,p_n$ 的字典序。

输入格式

第一行两个整数 $n,op$，$n$ 表示节点个数，$op$ 表示是否输出最小字典序。
接下来 $n-1$ 行每行两个整数 $u,v$ 表示一条边。

输出格式

首先输出一行一个整数表示最大总代价。
如果 $op=1$，则第二行再输出 $n$ 个数表示字典序最小的序列 $p_1,p_2,\dots,p_n$。

4 0
4 1
4 2
4 3

5

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

16
2 3 5 1 6 7 4

数据范围与提示

• 对于所有数据：$2\le n\le 2\times 10^5$，$op\in\{0,1\}$
• 本题采用捆绑测试。