在 Bajtazar 的花园里长着一棵树。它由 $n$ 个节点组成，编号从 $1$ 到 $n$，其中 $n$ 是偶数，并且有 $n - 1$ 条边，每条边直接连接两个节点。此外，正如树的通常情况一样，每对节点之间都存在唯一一条由不重复边组成的路径。

在 Byteland，国旗日即将到来，因此 Bajtazar 决定将他树的一半节点涂成白色，另一半涂成黑色，使其类似于 Byteland 的国旗（由于 Byteland 人重视和谐与对称，他们的国旗由一半白色和一半黑色组成）。我们将任何这样的涂色称为国旗涂色。

然而，如果 Bajtazar 没有一些奇思妙想，他就不是他自己了。他声称国旗涂色的美感取决于相同颜色节点对之间的距离之和，其中节点对之间的距离是指连接它们的路径上的边数量。

Bajtazar 希望这个和尽可能大。请帮助他找到这个最大和以及实现该和的任意一种国旗涂色方案！

输入格式

输入的第一行包含一个偶数 $n$ ($1 \le n \le 10^6$)，表示树中的节点数。接下来的 $n-1$ 行包含边的描述。这些行中的第 $i$ 行（对于 $1 \le i \le n-1$）包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示节点 $a_i$ 和 $b_i$ 由一条边直接相连。

输出格式

输出的第一行应包含给定树的国旗涂色中相同颜色节点对之间的最大距离之和。第二行应包含一个由 $n$ 个字符组成的字符串，描述实现该和的国旗涂色。在该字符串中，第 $i$ 个字符（对于 $1 \le i \le n$）如果节点 $i$ 被涂成白色则为 0，如果节点 $i$ 被涂成黑色则为 1。

样例

样例 1

输入

6
1 2
2 4
2 3
1 5
5 6

输出

14
011001

说明

样例解释：上例中的树如下图所示。节点根据上述样例输出进行涂色。白色节点之间的路径是节点 1 和 5 之间（长度 1）、1 和 4 之间（长度 2）以及 5 和 4 之间（长度 3）的路径。黑色节点之间的路径是节点 2 和 3 之间（长度 1）、2 和 6 之间（长度 3）以及 3 和 6 之间（长度 4）的路径。这些路径长度的总和为 $1 + 2 + 3 + 1 + 3 + 4 = 14$。可以验证，无法获得更大的同色节点间路径长度之和。

测试点

本题包含以下测试点： - 0a-0f：样例测试点。

子任务

如果你的答案仅第一行正确，你将获得该测试点 50% 的分数。你无需输出第二行即可获得这些分数。