In Bajtazar's garden grows a tree. It consists of $n$ nodes, numbered from $1$ to $n$, where $n$ is even, and has $n - 1$ edges, each directly connecting two nodes. Furthermore, as is usually the case in trees, there is exactly one simple path between every pair of nodes.

In Byteland, Flag Day is approaching, so Bajtazar decided to color half of the nodes of his tree white and half black, so that it resembles the flag of Byteland (as Bytelanders value harmony and symmetry, their flag consists of half white and half black color). We call any such coloring a flag coloring.

Bajtazar would not be himself, however, if he did not have his whims. He stated that the beauty of a flag coloring depends on the sum of distances between all pairs of nodes of the same color, where by the distance between a pair of nodes we mean the number of edges on the path connecting them.

Bajtazar wants this sum to be as large as possible. Help him and find this maximum sum and any flag coloring that achieves it!

Input

The first line of input contains one even number $n$ ($1 \le n \le 10^6$) representing the number of nodes in the tree. The next $n-1$ lines contain the description of the edges. The $i$-th of these lines (for $1 \le i \le n-1$) contains two integers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) meaning that nodes $a_i$ and $b_i$ are directly connected by an edge.

Output

The first line of output should contain the maximum sum of distances between pairs of nodes of the same color in a flag coloring of the given tree. The second line should contain a string consisting of $n$ characters describing the flag coloring that achieves this sum. In this string, the $i$-th character (for $1 \le i \le n$) is 0 if node $i$ is colored white, or 1 if it is colored black.

Examples

Input 1

6
1 2
2 4
2 3
1 5
5 6

Output 1

14
011001

Note

The tree from the example above is shown in the figure below. The nodes are colored according to the example output given above. The paths between white nodes are the paths between nodes 1 and 5 (length 1), 1 and 4 (length 2), and 5 and 4 (length 3). The paths between black nodes are the paths between nodes 2 and 3 (length 1), 2 and 6 (length 3), and 3 and 6 (length 4). The total sum of the lengths of these paths is $1 + 2 + 3 + 1 + 3 + 4 = 14$. It can be verified that it is not possible to obtain a larger sum of path lengths between nodes of the same color.

Grading

The test suite is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

If only the first line of your answer is correct, your solution will receive 50% of the points for the given test. You do not need to print the second line to receive these points.