Minimum Weight Assignment on a Tree

Given a tree (T) with (n) nodes, assign a positive integer weight (w_i) to each node such that for every edge ((u, v)), (w_u \neq w_v). The goal is to find an assignment that minimizes the total sum (\sum_{i=1}^{n} w_i). Since every tree is bipartite, one optimal solution is to partition the nodes into two sets and assign weights (1) and (2) respectively.

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 10^5)), the number of nodes in the tree. Each of the next (n-1) lines contains two integers (u) and (v) ((1 \leq u, v \leq n)) representing an edge between nodes (u) and (v).

outputFormat

Output two lines. The first line should contain the minimum total sum of weights. The second line should contain (n) integers, where the (i)-th integer represents the weight assigned to the (i)-th node. If there are multiple answers, output any valid solution.

sample

3
1 2
1 3

5
1 2 2