Problem H: RGBtree

Problem

$N$ 頂点 $N-1$ 辺からなる木があり、頂点には $1,2,\ldots,N$ の番号が、辺には $1,2,\ldots,N-1$ の番号がついており、 $i$ 番目の辺は頂点 $a_i$ と 頂点 $b_i$ を繋ぎます。
カトー君は、赤、緑、青の三色を用いてこの木の全ての頂点に色をつけます。
以下、'R' で赤、'G' で緑、'B' で青を表します。

あるパスに含まれる赤色で塗られた頂点の個数を $r$ 、緑色で塗られた頂点の個数を $g$ 、青色で塗られた頂点の個数を $b$ としたとき、 $\max (r,g,b)$ をそのパスのペナルティと定義します。
木全体のペナルティを「その木に含まれる、全てのパスのペナルティの最大値」と定義します。

あなたは、与えられた木に適切に色をつけた場合ペナルティの最小値はいくつになるか、カトー君の代わりに計算してあげることにしました。
ペナルティの最小値を求めてください。
また、そのペナルティを実現する色のつけ方を1つ求めてください。
複数の色のつけ方が存在する場合、どれを出力しても構いません。

Constraints

入力は以下の条件を満たす。

• $1 \leqq N \leqq 2 \times 10^{5}$
• $1 \leqq a_i, b_i \leqq N$
• 与えられるグラフは木であることが保証される。
• 入力は全て整数である。

Input

入力は以下の形式で標準入出力から与えられる。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

非負整数 $X$ 、文字列 $S$ を以下の形式で出力せよ。
ただし、 $X$ は達成可能な木全体のペナルティの最小値である。
$S$ は $i$ 文字目 $(1 \leqq i \leqq N)$ が頂点 $i$ の色を表す、ペナルティ $X$ を達成する塗り方を表す長さ $N$ の文字列である。
$S$ は、'R','G','B' の文字以外を含んではならない。

$X$
$S$

末尾の改行を忘れないこと。

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2
RGBR

この塗り方では、頂点1から頂点4までのパスのペナルティが一番大きく、最も多く含まれるのは 'R' で2個です。
よって、この木のペナルティは2で、これ以上ペナルティを小さくすることはできないため、 $X=2$ が答えになります。
$S$ としては他にも、 "RRBG" や "GGBB" といったものが正解として考えられます。

Sample Input 2

6
1 2
2 3
2 4
4 5
4 6

Sample Output 2

2
RGBRGB

どのように色を塗ってもペナルティを2より小さくすることはできません。
$S$ としては他にも、 "RRGGBB" といったものが正解として考えられます。

---