CF1244D.Paint the Tree

You are given a tree consisting of $n$ vertices. A tree is an undirected connected acyclic graph.

Example of a tree.

You have to paint each vertex into one of three colors. For each vertex, you know the cost of painting it in every color.

You have to paint the vertices so that any path consisting of exactly three distinct vertices does not contain any vertices with equal colors. In other words, let's consider all triples $(x, y, z)$ such that $x \neq y, y \neq z, x \neq z$, $x$ is connected by an edge with $y$, and $y$ is connected by an edge with $z$. The colours of $x$, $y$ and $z$ should be pairwise distinct. Let's call a painting which meets this condition good.

You have to calculate the minimum cost of a good painting and find one of the optimal paintings. If there is no good painting, report about it.

给你一棵包含 $n$ 个顶点的树。树是一种无向、连通且无环的图。

树的一个示例。

你需要将每个顶点染成三种颜色之一。对于每个顶点，你已知将其染成每种颜色的代价。

你需要对顶点进行染色，使得任意由恰好三个互不相同顶点构成的路径中，都不包含颜色相同的顶点。换言之，考虑所有三元组 $(x, y, z)$，满足 $x \neq y$，$y \neq z$，$x \neq z$，且 $x$ 与 $y$ 相邻、$y$ 与 $z$ 相邻。则 $x$、$y$、$z$ 的颜色必须两两不同。我们称满足该条件的染色方案为合法染色。

你需要计算合法染色的最小总代价，并构造出一种达到该最小代价的染色方案。若不存在合法染色方案，则报告这一点。

The first line contains one integer $n$ $(3 \le n \le 100\,000)$ — the number of vertices.

The second line contains a sequence of integers $c_{1, 1}, c_{1, 2}, \dots, c_{1, n}$ $(1 \le c_{1, i} \le 10^{9})$, where $c_{1, i}$ is the cost of painting the $i$-th vertex into the first color.

The third line contains a sequence of integers $c_{2, 1}, c_{2, 2}, \dots, c_{2, n}$ $(1 \le c_{2, i} \le 10^{9})$, where $c_{2, i}$ is the cost of painting the $i$-th vertex into the second color.

The fourth line contains a sequence of integers $c_{3, 1}, c_{3, 2}, \dots, c_{3, n}$ $(1 \le c_{3, i} \le 10^{9})$, where $c_{3, i}$ is the cost of painting the $i$-th vertex into the third color.

Then $(n - 1)$ lines follow, each containing two integers $u_j$ and $v_j$ $(1 \le u_j, v_j \le n, u_j \neq v_j)$ — the numbers of vertices connected by the $j$-th undirected edge. It is guaranteed that these edges denote a tree.

第一行包含一个整数 $n$ $(3 \le n \le 100\,000)$ —— 顶点的数量。

第二行包含一个整数序列 $c_{1, 1}, c_{1, 2}, \dots, c_{1, n}$ $(1 \le c_{1, i} \le 10^{9})$，其中 $c_{1, i}$ 表示将第 $i$ 个顶点染成第一种颜色的代价。

第三行包含一个整数序列 $c_{2, 1}, c_{2, 2}, \dots, c_{2, n}$ $(1 \le c_{2, i} \le 10^{9})$，其中 $c_{2, i}$ 表示将第 $i$ 个顶点染成第二种颜色的代价。

第四行包含一个整数序列 $c_{3, 1}, c_{3, 2}, \dots, c_{3, n}$ $(1 \le c_{3, i} \le 10^{9})$，其中 $c_{3, i}$ 表示将第 $i$ 个顶点染成第三种颜色的代价。

接下来有 $(n - 1)$ 行，每行包含两个整数 $u_j$ 和 $v_j$ $(1 \le u_j, v_j \le n, u_j \neq v_j)$ —— 表示第 $j$ 条无向边所连接的两个顶点的编号。保证这些边构成一棵树。

If there is no good painting, print $-1$.

Otherwise, print the minimum cost of a good painting in the first line. In the second line print $n$ integers $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 3)$, where the $i$-th integer should denote the color of the $i$-th vertex. If there are multiple good paintings with minimum cost, print any of them.

如果不存在合法的染色方案，则输出 $-1$。

否则，在第一行输出合法染色方案的最小总代价。在第二行输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 3)$，其中第 $i$ 个整数表示第 $i$ 个顶点的颜色。若存在多个总代价最小的合法染色方案，输出任意一个即可。

All vertices should be painted in different colors in the first example. The optimal way to do it is to paint the first vertex into color $1$, the second vertex — into color $3$, and the third vertex — into color $2$. The cost of this painting is $3 + 2 + 1 = 6$.

第一个例子中，所有顶点必须涂成不同的颜色。最优的涂色方式是：将第一个顶点涂成颜色 $1$，第二个顶点涂成颜色 $3$，第三个顶点涂成颜色 $2$。该涂色方案的代价为 $3 + 2 + 1 = 6$。