You are given a tree consisting of $n$ vertices. A tree is an undirected connected acyclic graph. [Image] 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.


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


-----Examples-----
Input
3
3 2 3
4 3 2
3 1 3
1 2
2 3

Output
6
1 3 2 

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

Output
-1

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

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

Difficulty: interview

Starter code:

Solutions:
from collections import deque
import sys
input = sys.stdin.readline


n = int(input())
cost = [list(map(int, input().split())) for i in range(3)]
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    if len(i) >= 3:
        print(-1)
        return

for i, j in enumerate(graph):
    if len(j) == 1:
        start = i
        break

visited = [-1]*n
visited[start] = 0
q = deque([start])

while q:
    pos = q.popleft()
    for next_pos in graph[pos]:
        if visited[next_pos] != -1:
            continue
        visited[next_pos] = (visited[pos] + 1) % 3
        q.append(next_pos)

ans = float("inf")
ind = [0, 1, 2]
for ptn in [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]:
    tmp_ans = 0
    for i in range(n):
        tmp_ans += cost[ptn[visited[i]]][i]
    if tmp_ans < ans:
        ans = tmp_ans
        ind = ptn[0:]

print(ans)
new_ans = [0]*n
for i in range(n):
    new_ans[i] = ind[visited[i]] + 1
print(*new_ans)

n = int(input())
c1 = [int(x) for x in input().split()]
c2 = [int(x) for x in input().split()]
c3 = [int(x) for x in input().split()]
c = {'1':c1, '2':c2, '3':c3}

a = {i:[] for i in range(1, n+1)}
for i in range(n-1):
    x, y = [int(x) for x in input().split()]
    a[x].append(y)
    a[y].append(x)

start = 0
bad = False
for k, v in a.items():
    l = len(v)
    if l > 2:
        bad = True
        break
    elif l == 1:
        start = k

if bad:
    print(-1)
else:
    prev = start
    cur = a[start][0]
    b = [prev]
    while True:
       b.append(cur)
       if len(a[cur]) == 1:
           break
       nxt = [x for x in a[cur] if x != prev][0]
       prev = cur
       cur = nxt
    
    ms = sum(c1)+sum(c2)+sum(c3)
    best_per = ''
    for per in {'123', '132', '231', '213', '312', '321'}:
        s = 0
        ci = 0
        for cur in b:
            cvet = per[ci]
            s += c[cvet][cur-1]
            ci = (ci+1)%3
        if s < ms:
            ms = s
            best_per = per

##    print(b)
    print(ms)
    ci = 0
    res = ['' for i in range(n+1)]
    for cur in b:
        cvet = best_per[ci]
        res[cur] = cvet
        ci = (ci+1) % 3
    for i in range(1, n+1):
        print(res[i],end = " ")
    


n = int(input())
c = [list(map(int, input().split())) for _ in range(3)]
g = [[] for _ in range(n)]
l = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
    l[a - 1] += 1
    l[b - 1] += 1
if max(l) > 2:
    print(-1)
    return
for i in range(n):
    if l[i] == 1:
        s = [i]
        break
dist = [-1] * n
dist[i] = 0
while s:
    d = s.pop()
    dist[d] %= 3
    for node in g[d]:
        if dist[node] == -1:
            s.append(node)
            dist[node] = dist[d] + 1
ans = float('inf')
for i1 in range(3):
    for i2 in range(3):
        if i1 == i2:
            continue
        for i3 in range(3):
            if i1 == i3 or i2 == i3:
                continue
            tmp = 0
            for j in range(n):
                tmp += c[(i1, i2, i3)[dist[j]]][j]
            if tmp < ans:
                idx = (i1, i2, i3)
                ans = tmp
print(ans)
for i in range(n - 1):
    print(idx[dist[i]] + 1, end=' ')
print(idx[dist[n - 1]] + 1)


from itertools import permutations
def cost(start, C):
    prev = start
    color = 0
    mycost = C[color][start]
    color = (color + 1) % 3
    cur = tree[start][0]
    for _ in range(n - 1):
        #print(prev, cur, tree[cur])
        glnext[prev] = cur
        mycost += C[color][cur]
        if prev != tree[cur][0]:
            prev = cur
            cur = tree[cur][0]
        elif len(tree[cur]) > 1:
            prev = cur
            cur = tree[cur][1]
        color = (color + 1) % 3
    return mycost


n = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
C = [c1, c2, c3]
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)
for node in tree:
    if len(node) > 2:
        print(-1)
        return
for i in range(n):
    if len(tree[i]) == 1:
        start = i
        break
best = 999999999999999999
glnext = [-1] * n
for p in permutations(list(range(3))):
    Cperm = [C[p[0]], C[p[1]], C[p[2]]]
    cst = cost(start, Cperm)
    if cst < best:
        best = cst
        ans = [-1] * n
        cur = start
        col = 0
        for _ in range(n):
            ans[cur] = p[col] + 1
            cur = glnext[cur]
            col = (col + 1) % 3
print(best)
print(' '.join(list(map(str, ans))))


#592_D

import sys

n = int(input())

vs = []

for i in range(0, 3):
    ln = [int(j) for j in sys.stdin.readline().rstrip().split(" ")]
    vs.append(ln)

vt = {}

f = True

for i in range(0, n - 1):
    edg = [int(j) for j in sys.stdin.readline().rstrip().split(" ")]
    if edg[0] in vt:
        vt[edg[0]].append(edg[1])
    else:
        vt[edg[0]] = [edg[1]]
    if edg[1] in vt:
        vt[edg[1]].append(edg[0])
    else:
        vt[edg[1]] = [edg[0]]

st = -1
for i in vt:
    if len(vt[i]) > 2:
        f = False
        break
    if len(vt[i]) == 1:
        st = i

if f:
    combos = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    m = -1
    ms = -1
    for i in range(0, len(combos)):
        cost = 0
        seq = [0] * (n)
        vert = st
        vis = {}
        for j in range(0, len(vs[0])):
            vis[vert] = True
            cost += vs[combos[i][j % 3] - 1][vert - 1]
            seq[vert - 1] = combos[i][j % 3]
            vert = vt[vert]
            if j == len(vs[0]) - 1:
                break
            if vert[0] in vis:
                vert = vert[1]
            else:
                vert = vert[0]
        if m == -1 or cost < m:
            m = cost
            ms = seq
    print(m)
    print(" ".join([str(i) for i in ms]))
else:
    print(-1)


class Vertex:
    def __init__(self, index):
        self.index = index
        self.neighbours = []
        self.color = None


def main():

    n = int(input())
    cols = []
    cols.append([int(z) for z in input().split()])
    cols.append([int(z) for z in input().split()])
    cols.append([int(z) for z in input().split()])

    tree = [Vertex(i) for i in range(n)]

    for _ in range(n-1):
        u1, u2 = [int(p) - 1 for p in input().split()]
        tree[u1].neighbours.append(u2)
        tree[u2].neighbours.append(u1)

    if any(len(vertex.neighbours) > 2 for vertex in tree):
        print("-1")
        return

    root = None
    for vertex in tree:
        if len(vertex.neighbours) == 1:
            root = vertex
            break

    current_group = 1
    prev_vertex = root.index
    vertex = tree[root.neighbours[0]]
    groups = [[root.index], [], []]

    while True:
        is_leaf = len(vertex.neighbours) == 1
        groups[current_group].append(vertex.index)
        if is_leaf:
            break
        current_group = (current_group + 1) % 3
        next_vertex_index = sum(vertex.neighbours) - prev_vertex
        prev_vertex = vertex.index
        vertex = tree[next_vertex_index]

    best_col_per_group = None
    best_price = None
    for col_per_group in [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]:
        price = 0
        for group_id in range(len(groups)):
            group_col = col_per_group[group_id] - 1
            for node_id in groups[group_id]:
                price += cols[group_col][node_id]
        if best_price is None or price < best_price:
            best_price = price
            best_col_per_group = col_per_group

    print(best_price)
    for color, group in zip(best_col_per_group, groups):
        for node_id in group:
            tree[node_id].color = color

    for node in tree:
        print(node.color, end=' ')

main()

n = int(input())
edge = [[] for _ in range(n)]
costs = [[] for _ in range(3)]
for i in range(3):
    costs[i] = [int(item) for item in input().split()]
for i in range(n - 1):
    u, v = [int(item) - 1 for item in input().split()]
    edge[u].append(v)
    edge[v].append(u)

beggining = None
for i, e in enumerate(edge):
    l = len(e)
    if l > 2:
        print(-1)
        return
    elif beggining is None and l == 1:
        beggining = i 

place = []
visited = [0] * n
node = beggining
while node != -1:
    place.append(node)
    visited[node] = 1
    ok = False
    for v in edge[node]:
        if visited[v]:
            continue
        node = v
        ok = True
    if not ok:
        break

c_ans = [0] * n
color = [0] * n
ans = 10 ** 18
for init_c in range(3):
    ret = 0
    c = init_c 
    for item in place:
        ret += costs[c][item]
        color[item] = c + 1
        c = (c + 1) % 3
    if ret < ans:
        ans = ret
        c_ans = color[:]
for init_c in range(3):
    ret = 0
    c = init_c 
    for item in place:
        ret += costs[c][item]
        color[item] = c + 1
        c = (c + 2) % 3
    if ret < ans:
        ans = ret
        c_ans = color[:]

print(ans)
print(" ".join([str(item) for item in c_ans]))

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())

c1 = list(map(int,input()[:-1].split()))
c2 = list(map(int,input()[:-1].split()))
c3 = list(map(int,input()[:-1].split()))

al = [list() for _ in range(n)]

for _ in range(n-1):
    u, v = list(map(int,input()[:-1].split()))
    al[u-1].append(v-1)
    al[v-1].append(u-1)

for i in range(n):
    if len(al[i]) > 2:
        print(-1)
        return
    elif len(al[i]) == 1:
        start = i

vis = [False for _ in range(n)]
sequence = []
stack = deque()
stack.append(start)

while len(stack)>0:
    u = stack.pop()
    sequence.append(u)
    vis[u] = True
    for v in al[u]:
        if not vis[v]:
            stack.append(v)

sums = [0]*6
seqs = [[c1,c2,c3],[c1,c3,c2],[c2,c1,c3],[c2,c3,c1],[c3,c1,c2],[c3,c2,c1]]
seqi = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

for i in range(n):
    for j in range(6):
        sums[j]+=seqs[j][i%3][sequence[i]]

mini = 0
mn = sums[0]

for i in range(len(sums)):
    if sums[i]< mn:
        mn = sums[i]
        mini = i
ans = [0]*n
for i in range(n):
    ans[sequence[i]] = seqi[mini][i%3]
print(mn)
print(*ans)



import itertools
import math


def main():
    tree = dict()
    n = int(input())
    c1 = list(map(int, input().split()))
    c2 = list(map(int, input().split()))
    c3 = list(map(int, input().split()))
    costs = [(c1[i], c2[i], c3[i]) for i in range(len(c1))]
    no_sol = False
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        if a not in tree:
            tree[a] = [b]
        else:
            tree[a].append(b)
        if b not in tree:
            tree[b] = [a]
        else:
            tree[b].append(a)
        if len(tree[a]) > 2:
            no_sol = True
        if len(tree[b]) > 2:
            no_sol = True

    if no_sol:
        print(-1)
        return

    for node in list(tree.keys()):
        if len(tree[node]) == 1:
            start = node
            break
            
    lst = [start]
    visited = [0] * (n +1)
    visited[node] = 1
    node = start
    while len(lst) < n:
        for i in tree[node]:
            if visited[i] == 0:
                visited[i] = 1
                lst.append(i)
                node = i
                break

    permutations = list(itertools.permutations([1,2,3], 3))
    cost = [0] * len(permutations)

    idx_permut = -1
    min_sum = math.inf
    for permut in range(len(permutations)):
        cost_sum = 0
        for i in range(len(lst)):
            list_cost = costs[lst[i]-1]
            cost_sum += list_cost[permutations[permut][i % 3]-1]
        cost[permut] = cost_sum
        if cost_sum < min_sum:
            min_sum = cost_sum
            idx_permut = permut


    d_sol = [0] * (len(lst) + 1)
    idx = 0
    my_perm = permutations[idx_permut]
    for i in lst:
        d_sol[i] = my_perm[idx % 3]
        idx += 1

    solution = d_sol[1:]

    print(min_sum)
    print(" ".join(map(str, solution)))


def __starting_point():
    main()

__starting_point()

n = int(input())
c = [list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split()))]
graph = []
for i in range(n):
    graph.append([])
sorted_graph = []
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    if len(graph[a]) > 2 or len(graph[b]) > 2:
        print(-1)
        return

for j in range(n):
    if len(graph[j]) == 1:
        sorted_graph.append(j)
        sorted_graph.append(graph[j][0])
        for _ in range(n - 2):
            for connection in graph[sorted_graph[-1]]:
                if connection != sorted_graph[-2]:
                    sorted_graph.append(connection)
                    break
        break

sorted_graph_indexes = [-1] * len(sorted_graph)
for i in range(len(sorted_graph_indexes)):
    sorted_graph_indexes[sorted_graph[i]] = i

sum = -1
signsum = 0
addsum = 0
for sign in range(-1, 2, 2):
    for add in range(3):
        lsum = 0
        for i in range(n):
            lsum += c[(add + sorted_graph_indexes[i] * sign) % 3][i]
        if sum == -1 or sum > lsum:
            sum = lsum
            signsum = sign
            addsum = add

print(sum)
for i in range(n):
    print((addsum + sorted_graph_indexes[i] * signsum) % 3 + 1, end=' ')


def main():
    n = int(input())
    color1 = [int(elm) for elm in input().split(" ")]
    color2 = [int(elm) for elm in input().split(" ")]
    color3 = [int(elm) for elm in input().split(" ")]

    graph = {}
    for i in range(n):
        graph[i] = []

    num_adjs = [0 for i in range(n)]
    for _ in range(n-1):
        p, q = map(int, input().split(" "))
        p -= 1
        q -= 1
        graph[p].append(q)
        graph[q].append(p)
        num_adjs[p] += 1
        num_adjs[q] += 1

    if max(num_adjs) >= 3:
        print(-1)
        return

    node_type = [0 for i in range(n)]
    first_nodes = [i for i, num_adj in enumerate(num_adjs) if num_adj == 1]
    if len(first_nodes) != 2:
        print(-1)
        return
    first_node, end_node = first_nodes

    junban = [first_node]
    parent = first_node
    jibun = graph[first_node][0]
    count = 0
    for i in range(n-1):
        junban.append(jibun)
        #print(end_node, jibun)

        if i == n-2:
            #assert jibun == end_node
            pass
        kids = graph[jibun]
        for kid in kids:
            if parent != kid:
                parent = jibun
                jibun = kid
                break
        count += 1
        
    
    colors = [color1, color2, color3]
    min_tensu = sum(color1) + sum(color2) + sum(color3)

    color_orders = [[0, 1, 2], [0, 2, 1], [1, 2, 0], [1, 0, 2], [2, 0, 1], [2, 1, 0]]
    for ci, color_order in enumerate(color_orders):
        cur_tensu = 0
        node_colors = [-1 for i in range(n)]
        for i, node_i in enumerate(junban):
            i = i % 3
            node_color = color_order[i]
            cost = colors[node_color][node_i]
            node_colors[node_i] = node_color 
            cur_tensu += cost
        if cur_tensu < min_tensu:
            min_ci = ci
            min_tensu = cur_tensu
            min_node_colors = node_colors

    print(min_tensu)
    print(" ".join([str(elm+1) for elm in min_node_colors]))



main()

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
c = []
for i in range(3):
    c.append(list(map(int, input().split())))
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    if len(graph[i])>2: print(-1); break
    if len(graph[i])==1: root = i
else:
    ls = [root, graph[root][0]]
    root = graph[root][0]
    while len(ls)!=n:
        for i in graph[root]:
            if i!=ls[-2]:
                ls.append(i)
                root = i
                break
    perm = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    for lis in perm:
        N = n-len(lis)
        for i in range(N):
            lis.append(lis[i%3])
    cost = []
    for lis in perm:
        temp = 0
        for i in range(n):
            temp+=c[lis[i]-1][ls[i]-1]
        cost.append(temp)
    m = min(cost)
    print(m)
    for i in range(6):
        if cost[i]==m:
           ls = {ls[j]: perm[i][j] for j in range(n)}
           for i in range(1, n+1):
               print(ls[i], end=' ')
           print()
           break


#!/usr/bin/env python3
import sys
from itertools import permutations
from math import inf

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())


n = oint()

c = []
for i in range(3):
    c.append(list(rint()))

adj = [set() for i in range(n)]
for i in range(n-1):
    u, v = rint()
    u -= 1
    v -= 1
    adj[u].add(v)
    adj[v].add(u)
for i in range(n):
    if len(adj[i]) >= 3:
        print(-1)
        return
    if len(adj[i]) == 1:
        start = i
minv = inf
i = [0]*3
ord = []
prev = -1
cur = start
for j in range(n):
    ord.append(cur)
    for next in adj[cur]:
        if next != prev:
            break
    prev = cur
    cur = next


for i[0], i[1], i[2] in permutations([0,1,2]):
    v = 0
    for j in range(n):
        v += c[i[j%3]][ord[j]]
    if v < minv:
        imin = i.copy()
        minv = v
ans = [0]*n
for j in range(n):
    ans[ord[j]] = imin[j%3] + 1
print(minv)
print(*ans)




#!/usr/bin/env python3
import sys
from itertools import permutations
from math import inf

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())


n = oint()

c = []
for i in range(3):
    c.append(list(rint()))

adj = [set() for i in range(n)]
for i in range(n-1):
    u, v = rint()
    u -= 1
    v -= 1
    adj[u].add(v)
    adj[v].add(u)
for i in range(n):
    if len(adj[i]) >= 3:
        print(-1)
        return
    if len(adj[i]) == 1:
        start = i
minv = inf
i = [0]*3
ord = []
cur = start
v = [0]*n
v[cur] = 1
for j in range(n):
    ord.append(cur)
    for next in adj[cur]:
        if v[next] == 0:
            v[next] = 1
            cur = next
            break

for i[0], i[1], i[2] in permutations([0,1,2]):
    v = 0
    for j in range(n):
        v += c[i[j%3]][ord[j]]
    if v < minv:
        imin = i.copy()
        minv = v
ans = [0]*n
for j in range(n):
    ans[ord[j]] = imin[j%3] + 1
print(minv)
print(*ans)




import sys
n=int(input())
a=[]
a1=[int(x) for x in input().split()]
a2=[int(x) for x in input().split()]
a3=[int(x) for x in input().split()]
a=[[0],a1,a2,a3]
#print(a)
adj=[[] for i in range(n+1)]
for i in range(n-1):
    u,v=list(map(int,input().split()))
    adj[u].append(v)
    adj[v].append(u)
#print(adj)    
for i in adj:
    if len(i)>2:
        print(-1)
        return
sumi=[0 for i in range(7)]
g=[[0 for j in range(n+1)] for i in range(6)]
for i in range(n):
    if len(adj[i])==1:
        p=i
        break
g[0][p]=1
g[0][adj[p][0]]=2
flag=3
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[0][adj[i][0]]==0 :
        g[0][adj[i][0]]=flag
        flag=6-flag-g[0][i]
        i=adj[i][0]
    else:
        g[0][adj[i][1]]=flag
        flag=6-flag-g[0][i]
        i=adj[i][1]
g[1][p]=2
g[1][adj[p][0]]=3
flag=1
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[1][adj[i][0]]==0 :
        g[1][adj[i][0]]=flag
        flag=6-flag-g[1][i]
        i=adj[i][0]
    else:
        g[1][adj[i][1]]=flag
        flag=6-flag-g[1][i]
        i=adj[i][1]
g[2][p]=1
g[2][adj[p][0]]=3
flag=2
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[2][adj[i][0]]==0 :
        g[2][adj[i][0]]=flag
        flag=6-flag-g[2][i]
        i=adj[i][0]
    else:
        g[2][adj[i][1]]=flag
        flag=6-flag-g[2][i]
        i=adj[i][1]
        
g[3][p]=3
g[3][adj[p][0]]=2
flag=1
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[3][adj[i][0]]==0 :
        g[3][adj[i][0]]=flag
        flag=6-flag-g[3][i]
        i=adj[i][0]
    else:
        g[3][adj[i][1]]=flag
        flag=6-flag-g[3][i]
        i=adj[i][1]

g[4][p]=3
g[4][adj[p][0]]=1
flag=2
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[4][adj[i][0]]==0 :
        g[4][adj[i][0]]=flag
        flag=6-flag-g[4][i]
        i=adj[i][0]
    else:
        g[4][adj[i][1]]=flag
        flag=6-flag-g[4][i]
        i=adj[i][1]

g[5][p]=2
g[5][adj[p][0]]=1
flag=3
i=adj[p][0]
for _ in range(n-1):
    if len(adj[i])==1:
        break
    if g[5][adj[i][0]]==0 :
        g[5][adj[i][0]]=flag
        flag=6-flag-g[5][i]
        i=adj[i][0]
    else:
        g[5][adj[i][1]]=flag
        flag=6-flag-g[5][i]
        i=adj[i][1]
#print(g) 
maxi=10**9*n+5
ans=0
i=1
for j in range(6):
    sumi=0
    
    for i in range(1,n+1):
        #print(i,j,g[j][i])
        sumi+=a[g[j][i]][i-1]
   # print(sumi)    
    if maxi>sumi  :
        maxi=sumi
        ans=j
        
print(maxi)
print(*g[ans][1:])



from collections import defaultdict as dd

n = int(input())
c1 = list(map(int,input().split()))
c2 = list(map(int,input().split()))
c3 = list(map(int,input().split()))

c1 = [None] + c1
c2 = [None] + c2
c3 = [None] + c3
c = [[None for _ in range(n+1)]] + [c1] + [c2] + [c3]

d = dd(lambda: [])

for _ in range(n-1):
    a,b = list(map(int,input().split()))
    d[a].append(b)
    d[b].append(a)

flag = True
root = None
for i in range(1,n+1):
    if len(d[i]) == 1:
        root = i
    if len(d[i]) >= 3:
        flag = False

if not flag:
    print(-1)
else:
    l1,l2,l3 = [],[],[]

    q = [(root,1)]
    s = set()

    while q:
        node,lv = q.pop(0)

        if node not in s:
            s.add(node)
            if lv == 1:
                l1.append(node)
            elif lv == 2:
                l2.append(node)
            elif lv == 3:
                l3.append(node)

            for v in d[node]:
                if lv == 1:
                    q.append((v,2))
                elif lv == 2:
                    q.append((v,3))
                elif lv == 3:
                    q.append((v,1))

    _min = 1e114 + 1
    cl = (0,0,0)

    for (cl1,cl2,cl3) in [(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)]:
        cost = sum([c[cl1][j] for j in l1]) + sum([c[cl2][j] for j in l2]) + sum([c[cl3][j] for j in l3])
        if cost < _min:
            _min = cost
            cl = (cl1,cl2,cl3)
        
    print(int(_min))
    cl1,cl2,cl3 = cl
    cl = [(i,cl1) for i in l1] + [(i,cl2) for i in l2] + [(i,cl3) for i in l3]
    cl.sort(key=lambda x:x[0])
    cl = [j for i,j in cl]
    print(*cl)


from collections import defaultdict, deque
from itertools import permutations


class Graph:
    def __init__(self):
        self.E = {}
        self.V = defaultdict(list)

    def put(self, v1, v2):
        if v1 not in self.E:
            self.E[v1] = 1
        if v2 not in self.E:
            self.E[v2] = 1
        self.V[v1].append(v2)
        self.V[v2].append(v1)

    def _adj(self, v1):
        return self.V[v1]

    def bfs(self, v):
        visited = set([v])
        path = [v]
        q = deque([v])
        while q:
            v1 = q.pop()
            for v2 in self._adj(v1):
                if v2 not in visited:
                    visited.add(v2)
                    path.append(v2)
                    q.appendleft(v2)

        return path


def __starting_point():
    n = int(input())
    cp = []
    for _ in range(3):
        cp.append(list(map(int, input().split(' '))))

    inv = False
    vert = defaultdict(int)
    graph = Graph()
    for _ in range(n - 1):
        v1, v2 = list(map(int, input().split(' ')))
        vert[v1] += 1
        if vert[v1] > 2:
            inv = True
            break
        vert[v2] += 1
        if vert[v2] > 2:
            inv = True
            break

        graph.put(v1, v2)

    if inv:
        print(-1)
    else:
        for key in vert:
            if vert[key] == 1:
                start = key
                break

        path = graph.bfs(start)

        min_cost = float('inf')
        min_cost_perm = (0, 1, 2)
        for p in permutations([0, 1, 2]):
            cur_cost = 0
            for i, v in enumerate(path):
                cur_cost += cp[p[i % 3]][v - 1]

            if cur_cost < min_cost:
                min_cost_perm = p
                min_cost = cur_cost

        # print(path, graph.V)
        ans = [0]*n
        for i, v in enumerate(path):
            ans[v - 1] = min_cost_perm[i % 3] + 1

        print(min_cost)
        print(' '.join(map(str, ans)))

__starting_point()

n=int(input())
c1=input().split()
c2=input().split()
c3=input().split()
for i in range(n):
    c1[i]=int(c1[i])
    c2[i]=int(c2[i])
    c3[i]=int(c3[i])
a=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    a[u-1].append(v-1)
    a[v-1].append(u-1)
#print(a)    
count1=0
count2=0
j=0
for i in range(n):
    if(len(a[i])==1):
        j=i
        count1+=1
    if(len(a[i])==2):
        count2+=1
if(count1==2 and count2==n-2):
    b=[]
    check=[0 for i in range(n)]
    while len(b)<n:
        b.append(j)
        check[j]=1
        if(len(b)==n):
            break
        if(check[a[j][0]]==0):j=a[j][0]
        else:j=a[j][1]
    # 6 cases
    # case 1 (1 2 3)
    ans1=0
    color1=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans1+=c1[b[i]]
            color1[b[i]]=1
        elif(i%3==1):
            ans1+=c2[b[i]]
            color1[b[i]]=2
        else:
            ans1+=c3[b[i]]
            color1[b[i]]=3
    # case 2 (3 1 2)
    ans2=0
    color2=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans2+=c3[b[i]]
            color2[b[i]]=3
        elif(i%3==1):
            ans2+=c1[b[i]]
            color2[b[i]]=1
        else:
            ans2+=c2[b[i]]   
            color2[b[i]]=2
    # case 3 (2 3 1)
    ans3=0
    color3=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans3+=c2[b[i]]
            color3[b[i]]=2
        elif(i%3==1):
            ans3+=c3[b[i]]
            color3[b[i]]=3
        else:
            ans3+=c1[b[i]]
            color3[b[i]]=1
    # case 4 (1 3 2)
    ans4=0
    color4=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans4+=c1[b[i]]
            color4[b[i]]=1
        elif(i%3==1):
            ans4+=c3[b[i]]
            color4[b[i]]=3
        else:
            ans4+=c2[b[i]]
            color4[b[i]]=2
    # case 5 (3 2 1)
    ans5=0
    color5=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans5+=c3[b[i]]
            color5[b[i]]=3
        elif(i%3==1):
            ans5+=c2[b[i]]
            color5[b[i]]=2
        else:
            ans5+=c1[b[i]]   
            color5[b[i]]=1
    # case 6 (2 1 3)
    ans6=0
    color6=[0 for i in range(n)]
    for i in range(n):
        if(i%3==0):
            ans6+=c2[b[i]]
            color6[b[i]]=2
        elif(i%3==1):
            ans6+=c1[b[i]]
            color6[b[i]]=1
        else:
            ans6+=c3[b[i]]  
            color6[b[i]]=3
    if(ans1==min(ans1,ans2,ans3,ans4,ans5,ans6)):
        print(ans1)
        print(*color1)
    elif(ans2==min(ans1,ans2,ans3,ans4,ans5,ans6)):
        print(ans2)
        print(*color2)
    elif(ans3==min(ans1,ans2,ans3,ans4,ans5,ans6)):
        print(ans3)
        print(*color3)
    elif(ans4==min(ans1,ans2,ans3,ans4,ans5,ans6)):
        print(ans4)
        print(*color4)
    elif(ans5==min(ans1,ans2,ans3,ans4,ans5,ans6)):
        print(ans5)
        print(*color5)
    else:
        print(ans6)
        print(*color6)
else:
    print(-1)

n = int(input())

c = [[0] + list(map(int, input().split())) for _ in range(3)]

e = [set() for u in range(n + 1)]

for i in range(n - 1):
	u, v = list(map(int, input().split()))
	e[u].add(v)
	e[v].add(u)

for i in range(1, n + 1):
	if len(e[i]) > 2:
		print(-1)
		return

for i in range(1, n + 1):
	if len(e[i]) == 1:
		S = i
		break

s = [S, next(iter(e[S]))]

for i in range(n - 2):
	u = s[-1]
	for v in e[u]:
		if v == s[-2]:
			continue
		s.append(v)
		break

ans, ans_d = 10 ** 100, []
d = [0 for _ in range(n + 1)]

for i in range(3):
	for j in range(3):
		if i != j:
			d[s[0]] = i + 1
			d[s[1]] = j + 1
			for k in range(2, n):
				d[s[k]] = 6 - (d[s[k - 1]] + d[s[k - 2]])
			w = sum([c[d[u] - 1][u] for u in range(1, n + 1)])
			if w < ans:
				ans = w
				ans_d = d[::]

print(ans)
print(*ans_d[1:])


n=int(input())
c1=list(map(int,input().split()))
c2=list(map(int,input().split()))
c3=list(map(int,input().split()))
ans=-1
edges={}
degree=[0]*n
for i in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    degree[u]+=1
    degree[v]+=1
    if u not in edges:
        edges[u]=[v]
    else :
        edges[u].append(v)
    if v not in edges:
        edges[v]=[u]
    else :
        edges[v].append(u)
import sys
if max(degree)>2:
    print(-1)
    return
bfs=[]
for i in range(n):
    if degree[i]==1:
        bfs.append(i)
        break
visited=[0]*n
visited[bfs[0]]=1
cost123=c1[bfs[0]]
cost132=c1[bfs[0]]
cost213=c2[bfs[0]]
cost231=c2[bfs[0]]
cost312=c3[bfs[0]]
cost321=c3[bfs[0]]
turn=1
colors=[0]*n
colors[bfs[0]]=1
while bfs:
    temp=[]
    for u in bfs:
        for v in edges[u]:
            if visited[v]==0:
                colors[v]=turn+1
                visited[v]=1
                temp.append(v)
                if turn==0:
                    cost123+=c1[v]
                    cost132+=c1[v]
                    cost213+=c2[v]
                    cost231+=c2[v]
                    cost312+=c3[v]
                    cost321+=c3[v]
                if turn==1:
                    cost123+=c2[v]
                    cost132+=c3[v]
                    cost213+=c1[v]
                    cost231+=c3[v]
                    cost312+=c1[v]
                    cost321+=c2[v]
                if turn==2:
                    cost123+=c3[v]
                    cost132+=c2[v]
                    cost213+=c3[v]
                    cost231+=c1[v]
                    cost312+=c2[v]
                    cost321+=c1[v]
                
    bfs=temp
    turn+=1
    turn=turn%3
x=min(cost123,cost132,cost213,cost231,cost312,cost321)
print(x)
if x==cost132:
    for i in range(n):
        if colors[i]==3:
            colors[i]=2
        elif colors[i]==2:
            colors[i]=3
elif x==cost213:
    for i in range(n):
        if colors[i]==1:
            colors[i]=2
        elif colors[i]==2:
            colors[i]=1
elif x==cost231:
    for i in range(n):
        if colors[i]==1:
            colors[i]=2
        elif colors[i]==2:
            colors[i]=3
        else :
            colors[i]=1
elif x==cost312:
    for i in range(n):
        if colors[i]==1:
            colors[i]=3
        elif colors[i]==2:
            colors[i]=1
        else :
            colors[i]=2
elif x==cost321:
    for i in range(n):
        if colors[i]==1:
            colors[i]=3
        elif colors[i]==3:
            colors[i]=1
print(*colors,sep=" ")
    

# -*- coding: utf-8 -*-

import sys
from itertools import permutations

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
C1 = LIST()
C2 = LIST()
C3 = LIST()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

start = 0
for i in range(N):
    if len(nodes[i]) >= 3:
        print(-1)
        return
    if len(nodes[i]) == 1:
        start = i

Cs = [[] for i in range(3)]
stack = [(start, -1)]
while stack:
    u, prev = stack.pop()
    Cs[0].append(C1[u])
    Cs[1].append(C2[u])
    Cs[2].append(C3[u])
    for v in nodes[u]:
        if v != prev:
            stack.append((v, u))

# def rec(u, prev):
#     Cs[0].append(C1[u])
#     Cs[1].append(C2[u])
#     Cs[2].append(C3[u])
#     for v in nodes[u]:
#         if v != prev:
#             rec(v, u)
# rec(start, -1)

mn = INF
p = []
for perm in permutations(list(range(3))):
    sm = 0
    for i in range(N):
        sm += Cs[perm[i%3]][i]
    if mn > sm:
        mn = min(mn, sm)
        p = perm

ans = [0] * N
stack = [(start, -1, 0)]
while stack:
    u, prev, cnt = stack.pop()
    ans[u] = p[cnt%3] + 1
    for v in nodes[u]:
        if v != prev:
            stack.append((v, u, cnt+1))

# def rec2(u, prev, cnt):
#     ans[u] = p[cnt%3] + 1
#     for v in nodes[u]:
#         if v != prev:
#             rec2(v, u, cnt+1)
# rec2(start, -1, 0)

print(mn)
print(*ans)