在一个虚构的王国中有 $n$ 座城市。所有城市通过 $n - 1$ 条双向道路连接。每条道路在每个方向上的通行费均为 $1$ 个单位。

最近，市民们开始质疑为什么穿越全国的通行费用如此昂贵。国王决定将一些道路设为免费。他希望为每座城市选择一条道路，将其在该城市出发方向上的通行费设为免费。他的目标是最小化所有城市之间直接道路旅行中的最大总通行费。你需要帮助他！

输入格式

第一行包含一个正整数 $n$ ($2 \le n \le 200\,000$)，表示虚构王国中城市的数量。

接下来的 $n - 1$ 行，每行包含两个正整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示连接城市 $a_i$ 和 $b_i$ 的第 $i$ 条道路。

输出格式

第一行输出一个整数 $d$，表示从一个城市到另一个城市最昂贵的道路旅行所需支付的最小总通行费。

下一行输出 $n$ 个整数 $e_i$，表示为第 $i$ 座城市选择的免费道路的索引。如果未为第 $i$ 座城市选择任何道路，则输出 $e_i = -1$。

样例

样例输入 1

4
1 2
1 3
1 4

样例输出 1

1
-1 1 2 3

样例输入 2

3
1 2
2 3

样例输出 2

1
1 -1 2