RGB트리

The RGB Tree, a landmark of RGB Street, has $N$ light bulbs. The bulbs are numbered 1 to $N$, and each bulb can emit red, green, or blue light. The bulbs are connected in a tree structure, and adjacent bulbs must emit light of different colors. Given the beauty of each bulb for each color, find a coloring that maximizes the sum of beauty.

The first line contains the number of bulbs $N$. ($1 \leq N \leq 500\,000$)

From the second line to the $N$th line, each line contains two bulb numbers separated by a space, meaning the two bulbs are adjacent.

From the $(N+1)$th line to the $2N$th line, each line contains three integers separated by spaces. On line $N+i$, $r_i$, $g_i$, and $b_i$ are the beauty values of bulb $i$ when it emits red, green, and blue light. ($1 \leq r_i, g_i, b_i \leq 1\,000$)

On the first line, print the maximum possible sum of beauty over all bulbs.

On the second line, print the colors of bulbs 1 to $N$ in order, without spaces. Print R for red, G for green, and B for blue. If several answers exist, print any of them.