RGB트리

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로 출력한다. 가능한 답이 여러 가지라면 아무거나 출력한다.