시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB29614812349.200%

문제

RGB거리의 랜드마크인 RGB트리에는 전구가 $N$개 있다. 전구의 번호는 $1$번부터 $N$번까지이고, 각 전구는 빨강, 초록, 파랑 중 한 색의 빛을 낼 수 있다. 전구들은 트리 구조를 이루도록 연결되어 있으며, 인접한 전구끼리는 다른 색의 빛을 내야 한다. 각 전구가 내는 빛의 색에 따른 아름다움이 주어졌을 때, 아름다움의 합이 최대가 되도록 하는 방법을 구하시오.

입력

첫째 줄에 전구의 개수 $N$이 주어진다. $(1\leq N\leq 500\,000)$

둘째 줄부터 $N$째 줄에는 인접한 두 전구의 번호가 공백으로 구분되어 주어진다.

$N+1$째 줄부터 $2N$째 줄에는 각 줄에 세 정수가 공백으로 구분되어 주어진다. $N+i$째 줄에는 $i$번 전구가 빨강, 초록, 파랑 빛을 낼 때의 아름다움 $r_i,g_i,b_i$가 주어진다. $(1 \leq r_i,g_i,b_i \leq 1\,000)$

출력

첫째 줄에 모든 전구의 아름다움의 합의 최댓값을 출력한다.

둘째 줄에 아름다움이 최대가 될 때 전구의 색을 $1$번부터 순서대로 공백 없이 출력한다. 빨강일 경우 R, 초록일 경우 G, 파랑일 경우 B로 출력한다. 가능한 답이 여러 가지라면 아무거나 출력한다.

예제 입력 1

8
1 2
1 3
1 4
1 5
5 6
6 7
4 8
69 67 74
9 22 55
99 24 29
53 59 33
49 12 48
19 57 24
17 88 93
8 85 7

예제 출력 1

558
GBRRRGBG