問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
頂点数 n の木が与えられます。
隣り合う頂点が異なる色になるように、すべての頂点に色を塗るとき、その最小の色数と、その塗り分け方を 1 つ求めてください。
なお、正しい塗り分け方であれば、どのような塗り分け方を出力しても構いません。
n
a_1 b_1
...
a_{n - 1} b_{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)
・ 与えられるグラフは木である
4
1 2
2 3
2 4
2
1
2
1
1