题目描述

Dynów 山区有 $n$ 座山峰，编号 $1$ 到 $n$。部分山峰之间由步道直接相连，走过一条步道需要一小时。共有恰好 $n-1$ 条步道，并且任意两座山峰之间都可以互相到达，因此这些山峰和步道构成一棵树。

一些不太愿意爬山的参加者想编一个“听起来很壮观”的旅行故事。他们希望找到一个排列 $a_1,a_2,\ldots,a_n$，其中 $1$ 到 $n$ 每个编号恰好出现一次，并声称自己依次从 $a_1$ 前往 $a_2$、再到 $a_3$，……，到达 $a_n$ 后再回到 $a_1$。

两个山峰之间的路程定义为树上最短路径的边数。请使上述闭合路线的总长度最大，并给出一个达到最大值的排列。

输入格式

第一行一个整数 $n$，$1\le n\le100000$。

接下来 $n-1$ 行，每行两个整数 $a_i,b_i$，表示山峰 $a_i$ 与 $b_i$ 之间有一条步道。

输出格式

输出两行。

第一行输出最大可能的路线长度。

样例输入

6
1 2
1 3
1 4
1 5
5 6

样例输出

12