塗り分け (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

頂点数 n の木が与えられます。
隣り合う頂点が異なる色になるように、すべての頂点に色を塗るとき、その最小の色数と、その塗り分け方を 1 つ求めてください。

なお、正しい塗り分け方であれば、どのような塗り分け方を出力しても構いません。

入力される値

n
a_1 b_1
...
a_{n - 1} b_{n - 1}

・ 1 行目に、頂点の個数を表す整数 n が与えられます。
・続く n - 1 行では、木構造の辺を表す頂点の番号の組 a_i, b_i が半角スペース区切りで与えられます。(1 ≦ i ≦ n - 1)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 n + 1 行出力してください。

1 行目に、最小の色数を表す整数 k を出力してください。
続く n 行に、i + 1 行目には i 番目の頂点の色を表す整数を半角スペース区切りで出力してください。
頂点の色は、1 以上 k 以下の整数としてください。

また、末尾に改行を入れ、余計な文字を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100,000 = 10^5
・ 1 ≦ a_i, b_i ≦ n
・ a_i ≠ b_i
・ (a_i, b_i) ≠ (a_j, b_j), (a_i, b_i) ≠ (b_j, a_j) (i ≠ j)
・与えられるグラフは木である