Paint the Tree

Description:

Input:

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.

Output:

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.

Sample Input:

3
3 2 3
4 3 2
3 1 3
1 2
2 3

Sample Output:

6
1 3 2 

Sample Input:

5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 3

Sample Output:

-1

Sample Input:

5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 4

Sample Output:

9
1 3 2 1 3 

Note:

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$$$.