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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Implementation

Complete search

Tree algorithms

Dynamic programming


Solutions:
def main():
	from sys import stdin, stdout
	n = int(stdin.readline())
	from itertools import chain
	c1 = tuple(map(int, input().split()))
	c2 = tuple(map(int, input().split()))
	c3 = tuple(map(int, input().split()))
	tree = tuple(([] for _ in range(n)))
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		tree[u].append(v)
		tree[v].append(u)
		if len(tree[u]) > 2 or len(tree[v]) > 2:
			print('-1')
			break
	else:
		for u in range(n):
			if len(tree[u]) < 2:
				v = u
				break
		ans = [0] * n
		ansi = 1
		cost = tuple(([0, 0, 0] for _ in range(4)))
		w = 0
		for _ in range(n):
			ans[v] = ansi
			cost[1][ansi] += c1[v]
			cost[2][ansi] += c2[v]
			cost[3][ansi] += c3[v]
			ansi = (ansi + 1) % 3
			if len(tree[v]) == 1:
				w = v
				(v,) = tree[v]
			else:
				(v, w) = (next((x for x in tree[v] if x != w)), v)
		pal = min(((p1, p2, p3, cost[p1][0] + cost[p2][1] + cost[p3][2]) for p1 in (1, 2, 3) for p2 in (1, 2, 3) if p1 != p2 for p3 in (6 - p1 - p2,)), key=lambda x: x[3])
		print(pal[3])
		print(*(pal[ansi] for ansi in ans))
main()


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) = map(int, input().split())
	e[u].add(v)
	e[v].add(u)
for i in range(1, 1 + n):
	if len(e[i]) > 2:
		print(-1)
		exit()
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(map(lambda u: c[d[u] - 1][u], range(1, n + 1)))
			if w < ans:
				ans = w
				ans_d = d[:]
print(ans)
print(*ans_d[1:])


from sys import stdin, stdout
from collections import Counter
import math

def rsingle_int():
	return int(stdin.readline().rstrip())

def rmult_int():
	return [int(x) for x in stdin.readline().rstrip().split()]

def rmult_str():
	return stdin.readline().rstrip().split()

def r_str():
	return stdin.readline().rstrip()

def rsingle_char():
	return stdin.read(1)

def sortFirst(val):
	return val[0]

def main():
	n = rsingle_int()
	cols = [[] for _ in range(3)]
	cols[0] = rmult_int()
	cols[1] = rmult_int()
	cols[2] = rmult_int()
	nodes = [[] for _ in range(n)]
	edges = []
	for _ in range(n - 1):
		(a, b) = rmult_int()
		edges.append((a - 1, b - 1))
		nodes[a - 1].append(b - 1)
		nodes[b - 1].append(a - 1)
	possible = True
	for node in nodes:
		if len(node) > 2:
			possible = False
			break
	if not possible:
		print(-1)
	else:
		root = None
		for (i, node) in enumerate(nodes):
			if len(node) == 1:
				root = i
		if root:
			color_threes = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
			min_colors = None
			min_cost = math.inf
			for color_three in color_threes:
				prev_prev = root
				prev = nodes[root][0]
				cost = cols[color_three[0]][prev_prev] + cols[color_three[1]][prev]
				colors = [None for _ in nodes]
				colors[prev_prev] = color_three[0] + 1
				colors[prev] = color_three[1] + 1
				i = 2
				while len(nodes[prev]) == 2:
					curr_col = color_three[i]
					i = (i + 1) % 3
					(a, b) = nodes[prev]
					current = a
					if a == prev_prev:
						current = b
					cost += cols[curr_col][current]
					colors[current] = curr_col + 1
					prev_prev = prev
					prev = current
				if cost < min_cost:
					min_cost = cost
					min_colors = colors
			print(min_cost)
			print(*min_colors)
		else:
			print(-1)
main()


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

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def calc(self, c1, c2):
		if c1 == 1 and c2 == 2:
			return 3
		elif c1 == 1:
			return 2
		elif c1 == 2 and c2 == 3:
			return 1
		elif c1 == 2:
			return 3
		elif c1 == 3 and c2 == 1:
			return 2
		else:
			return 1

	def bfs(self, root, c1, c2):
		self.parent = [-1 for i in range(self.n)]
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		color[root] = c1 + 1
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					if self.parent[element] == -1:
						color[i] = c2 + 1
					else:
						color[i] = self.calc(color[element], color[self.parent[element]])

def value(arr):
	ans = 0
	for i in range(n):
		if arr[i] == 1:
			ans += a1[i]
		elif arr[i] == 2:
			ans += a2[i]
		else:
			ans += a3[i]
	return ans
n = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
g = Graph(n, False)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g.addEdge(a - 1, b - 1)
dp = [0] * n
root = -1
for i in range(n):
	if len(g.graph[i]) == 1:
		root = i
	elif len(g.graph[i]) > 2:
		root = -1
		break
if root == -1:
	print(-1)
	exit()
(ans, fans) = (10 ** 18, [])
color = [0] * n
g.bfs(root, 0, 1)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
color = [0] * n
g.bfs(root, 0, 2)
value(color)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
color = [0] * n
g.bfs(root, 1, 0)
value(color)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
color = [0] * n
g.bfs(root, 1, 2)
value(color)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
color = [0] * n
g.bfs(root, 2, 1)
value(color)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
color = [0] * n
g.bfs(root, 2, 0)
value(color)
if value(color) < ans:
	ans = value(color)
	fans = color[:]
print(ans)
print(*fans)


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) = 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 = 1e+114 + 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)


import sys
input = sys.stdin.readline
n = int(input())
C = []
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
E = [[] for i in range(n)]
COUNT = [0] * n
for i in range(n - 1):
	(x, y) = map(int, input().split())
	E[x - 1].append(y - 1)
	E[y - 1].append(x - 1)
	COUNT[x - 1] += 1
	COUNT[y - 1] += 1
if max(COUNT) >= 3:
	print(-1)
	sys.exit()
for i in range(n):
	if len(E[i]) == 1:
		start = i
		break
LIST = [start, E[start][0]]
USE = [0] * n
USE[start] = 1
USE[E[start][0]] = 1
while True:
	now = LIST[-1]
	if len(E[now]) == 1:
		break
	for x in E[now]:
		if USE[x] == 0:
			USE[x] = 1
			LIST.append(x)
ANS = 1 << 60
MINABC = [-1, -1, -1]
for (a, b, c) in [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]:
	score = 0
	for i in range(n):
		if i % 3 == 0:
			score += C[a][LIST[i]]
		elif i % 3 == 1:
			score += C[b][LIST[i]]
		else:
			score += C[c][LIST[i]]
	if ANS > score:
		ANS = score
		MINABC = [a, b, c]
print(ANS)
ANSLIST = [0] * n
(a, b, c) = MINABC
for i in range(n):
	if i % 3 == 0:
		ANSLIST[LIST[i]] = a + 1
	elif i % 3 == 1:
		ANSLIST[LIST[i]] = b + 1
	else:
		ANSLIST[LIST[i]] = c + 1
print(*ANSLIST)


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):
		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) = 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)
		exit(0)
for i in range(n):
	if len(tree[i]) == 1:
		start = i
		break
best = 999999999999999999
glnext = [-1] * n
for p in permutations(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))))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import *

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def val():
	return int(input().rstrip('\n'))

def st():
	return input().rstrip('\n')

def sttoli():
	return [int(i) for i in input().rstrip('\n')]
visited = {}

def giveind(b, c):
	for _____ in range(3):
		if b != _____ and c != _____:
			return _____

def dfs(a, d, prev, temp):
	global visited
	q = deque()
	q.append([a, prev[0], prev[1]])
	while q:
		(root, a, b) = q.pop()
		if root not in visited:
			visited[root] = 1
			temp[root - 1] = giveind(a, b)
			(a, b) = (b, temp[root - 1])
			for j in d[root]:
				q.append([j, a, b])

def givecost(c, a):
	tot = 0
	for (ind, i) in enumerate(a):
		tot += c[i][ind]
	return tot
n = val()
c1 = li()
c2 = li()
c3 = li()
c = [c1, c2, c3]
d = defaultdict(list)
for i in range(n - 1):
	(a, b) = sorted(li())
	d[a].append(b)
	d[b].append(a)
	if len(d[a]) > 2 or len(d[b]) > 2:
		print(-1)
		exit()
pairs = [[0, 1], [1, 2], [0, 2], [1, 0], [2, 1], [2, 0]]
micost = 1000000000001000
temp = [1] * n
ind = [0, 1, 2]
for i in pairs:
	temp[0] = i[0]
	visited = {}
	visited[1] = 1
	temp[d[1][0] - 1] = i[1]
	visited[d[1][0]] = 1
	if len(d[1]) > 1:
		prev = [i[1], i[0]]
		dfs(d[1][1], d, prev, temp)
		prev = prev[::-1]
		if d[d[1][0]][0] != 1:
			dfs(d[d[1][0]][0], d, prev, temp)
		else:
			try:
				dfs(d[d[1][0]][1], d, prev, temp)
			except:
				afszxgeadgaedvzx = 2
	else:
		prev = [i[0], i[1]]
		if d[d[1][0]][0] == 1:
			dfs(d[d[1][0]][1], d, prev, temp)
		else:
			dfs(d[d[1][0]][0], d, prev, temp)
	cost = givecost(c, temp)
	if cost < micost:
		micost = cost
		ans = [i + 1 for i in temp]
print(micost)
print(*ans)


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
		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())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = [a, b, c]
s = {}
s1 = set()
for _ in range(n - 1):
	(x1, x2) = map(int, input().split())
	x3 = s.get(x1, 0)
	if x3 == 0:
		s[x1] = {x2}
		s1.add(x1)
	else:
		x3.add(x2)
		s1.remove(x1) if x1 in s1 else None
		if len(x3) > 2:
			print(-1)
			exit(0)
		else:
			s[x1] = x3
	x4 = s.get(x2, 0)
	if x4 == 0:
		s[x2] = {x1}
		s1.add(x2)
	else:
		x4.add(x1)
		s1.remove(x2) if x2 in s1 else None
		if len(x4) > 2:
			print(-1)
			exit(0)
		else:
			s[x2] = x4
s2 = s1.pop()
s3 = [a[s2 - 1], a[s2 - 1], b[s2 - 1], b[s2 - 1], c[s2 - 1], c[s2 - 1]]
flag = [[1, 1, 2, 2, 3, 3], [2, 3, 1, 3, 1, 2], [3, 2, 3, 1, 2, 1]]
f = 1
used = {s2}
p = [s2]
while 1:
	x5 = s.get(s2)
	x6 = x5 - used
	if len(x6) == 0:
		r1 = min(s3)
		r2 = s3.index(r1)
		path = ['1 2 3 ', '1 3 2 ', '2 1 3 ', '2 3 1 ', '3 1 2 ', '3 2 1 ']
		print(r1)
		p1 = (path[r2] * (n // 3) + path[r2][:n % 3 * 2]).split(' ')[:-1]
		p2 = zip(*sorted(zip(p, p1)))
		print(' '.join(list(p2)[1]))
		exit(0)
	else:
		x7 = x6.pop()
		p.append(x7)
		for i in range(6):
			s3[i] += d[flag[f][i] - 1][x7 - 1]
		f = (f + 1) % 3
		s2 = x7
		used.add(x7)


from typing import List
import math

class Node:

	def __init__(self):
		self.childs: List[int] = []
		self.cost: List[int] = [0] * 3

def paint_the_tree_solve():
	comb = [[0, 1, 2], [1, 0, 2], [0, 2, 1], [2, 0, 1], [1, 2, 0], [2, 1, 0]]
	n = int(input())
	tree: List[Node] = [Node() for _ in range(n)]
	for i in range(3):
		c1_costs = [int(a) for a in input().split(' ')]
		for c in range(n):
			tree[c].cost[i] = c1_costs[c]
	for i in range(n - 1):
		(a, b) = [int(a) - 1 for a in input().split(' ')]
		if len(tree[a].childs) == 2 or len(tree[b].childs) == 2:
			print(-1)
			exit()
		tree[a].childs.append(b)
		tree[b].childs.append(a)
	for i in range(n):
		if len(tree[i].childs) == 1:
			k = i
			break
	final_ans = math.inf
	final_colors = []
	for c in comb:
		colors = [-1] * n
		node = k
		ans = 0
		colors[node] = c[0]
		ans += tree[node].cost[c[0]]
		node = tree[node].childs[0]
		colors[node] = c[1]
		ans += tree[node].cost[c[1]]
		for i in range(2, n):
			for child in tree[node].childs:
				if colors[child] == -1:
					colors[child] = c[i % 3]
					ans += tree[child].cost[c[i % 3]]
					node = child
		if ans < final_ans:
			final_colors = colors
			final_ans = ans
	print(final_ans)
	print(' '.join([str(a + 1) for a in final_colors]))
paint_the_tree_solve()


n = int(input())
c = [list(map(int, input().split())) for i in range(3)]
edges = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
for i in range(n):
	if len(edges[i]) > 2:
		print(-1)
		exit()
path = []
for i in range(n):
	if len(edges[i]) == 1:
		path.append(i)
		break
seen = [False] * n
seen[path[-1]] = True
while True:
	for i in edges[path[-1]]:
		if not seen[i]:
			path.append(i)
			seen[i] = True
			break
	else:
		break
d = [[0] * n for i in range(3)]
for i in range(3):
	now = 0
	for j in path:
		d[i][now] = c[i][j]
		now += 1
from itertools import permutations
ans = 10 ** 30
now = []
for i in permutations(range(3), 3):
	ans_sub = 0
	now_sub = [0] * n
	for j in range(n):
		now_sub[path[j]] = i[j % 3] + 1
		ans_sub += d[i[j % 3]][j]
	if ans_sub < ans:
		ans = ans_sub
		now = now_sub
print(ans)
print(' '.join(map(str, now)))


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


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
n = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
col = [c1, c2, c3]
graph = [[] for s in range(n)]
for s in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
if len(max(graph, key=len)) >= 3:
	print(-1)
else:
	root = -1
	for s in range(n):
		if len(graph[s]) == 1:
			root = s
			break
	minans = 10 ** 20
	perm = [0, 1, 2]
	for s in range(3):
		alt = [0, 1, 2]
		alt.remove(s)
		perm1 = [s] + alt
		ans1 = col[perm1[0]][root]
		queue = deque([root])
		vis = set([root])
		while len(queue) > 0:
			v0 = queue.popleft()
			for node in graph[v0]:
				if not node in vis:
					ans1 += col[perm1[len(vis) % 3]][node]
					queue.append(node)
					vis.add(node)
		alt.reverse()
		perm2 = [s] + alt
		ans2 = col[perm2[0]][root]
		queue = deque([root])
		vis = set([root])
		while len(queue) > 0:
			v0 = queue.popleft()
			for node in graph[v0]:
				if not node in vis:
					ans2 += col[perm2[len(vis) % 3]][node]
					queue.append(node)
					vis.add(node)
		if ans1 <= minans:
			minans = ans1
			perm = perm1
		if ans2 <= minans:
			minans = ans2
			perm = perm2
	paint = [0 for s in range(n)]
	queue = deque([root])
	vis = set([root])
	paint[root] = perm[0] + 1
	while len(queue) > 0:
		v0 = queue.popleft()
		for node in graph[v0]:
			if not node in vis:
				paint[node] = perm[len(vis) % 3] + 1
				queue.append(node)
				vis.add(node)
	print(minans)
	print(*paint)


n = int(input())
c = list()
edges = [[] for _ in range(n)]
for k in range(3):
	c.append([int(x) for x in input().split()])
for _ in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	edges[a].append(b)
	edges[b].append(a)
flag = True
ends = list()
for i in range(n):
	if len(edges[i]) > 2:
		flag = False
	if len(edges[i]) == 1:
		ends.append(i)
if flag:
	group = [-1] * n
	tmp = ends[0]
	group[tmp] = 0
	count = 1
	while tmp != ends[1]:
		for x in edges[tmp]:
			if group[x] == -1:
				tmp = x
		group[tmp] = count % 3
		count += 1
	coloredSum = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
	for i in range(n):
		coloredSum[group[i]][0] += c[0][i]
		coloredSum[group[i]][1] += c[1][i]
		coloredSum[group[i]][2] += c[2][i]
	ans = coloredSum[0][0] + coloredSum[1][1] + coloredSum[2][2]
	grouptocolour = [1, 2, 3]
	if coloredSum[0][0] + coloredSum[1][2] + coloredSum[2][1] < ans:
		ans = coloredSum[0][0] + coloredSum[1][2] + coloredSum[2][1]
		grouptocolour = [1, 3, 2]
	if coloredSum[0][1] + coloredSum[1][0] + coloredSum[2][2] < ans:
		ans = coloredSum[0][1] + coloredSum[1][0] + coloredSum[2][2]
		grouptocolour = [2, 1, 3]
	if coloredSum[0][1] + coloredSum[1][2] + coloredSum[2][0] < ans:
		ans = coloredSum[0][1] + coloredSum[1][2] + coloredSum[2][0]
		grouptocolour = [2, 3, 1]
	if coloredSum[0][2] + coloredSum[1][0] + coloredSum[2][1] < ans:
		ans = coloredSum[0][2] + coloredSum[1][0] + coloredSum[2][1]
		grouptocolour = [3, 1, 2]
	if coloredSum[0][2] + coloredSum[1][1] + coloredSum[2][0] < ans:
		ans = coloredSum[0][2] + coloredSum[1][1] + coloredSum[2][0]
		grouptocolour = [3, 2, 1]
	print(ans)
	for x in group:
		print(grouptocolour[x], end=' ')
else:
	print(-1)


import sys
input = sys.stdin.readline
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(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=' ')


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, temp, v, visited, depth, parent):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				depth[i] = depth[v] + 1
				parent[i] = v
				temp = (yield self.DFSUtil(temp, i, visited, depth, parent))
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)
t = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
c = list(zip(c1, c2, c3))
n = len(c1)
G = Graph(len(c1))
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	G.addEdge(u, v)
degrees = [len(i) for i in G.adj]
patterns = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
if max(degrees) > 2:
	print(-1)
else:
	ind = -1
	for i in range(0, len(degrees)):
		if degrees[i] == 1:
			ind = i
			break
	depth = [0] * n
	parent = [0] * n
	visited = [False for _ in range(n)]
	G.DFSUtil([], ind, visited, depth, parent)
	total = 1e+18
	final = []
	for p in patterns:
		temp = 0
		ans = []
		for i in range(0, n):
			temp = temp + c[i][p[depth[i] % 3]]
			ans.append(p[depth[i] % 3] + 1)
		if temp < total:
			total = temp
			final = ans
	print(total)
	print(*final)


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))
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))
print(mn)
print(*ans)


import sys
from itertools import permutations
from math import inf

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)


n = int(input())
r1 = input()
r1 = r1.split()
r2 = input()
r2 = r2.split()
r3 = input()
r3 = r3.split()
costs = list()
vertices = list()
powers = list()
i = 0
while i < n:
	costs.append(list())
	costs[i].append(int(r1[i]))
	costs[i].append(int(r2[i]))
	costs[i].append(int(r3[i]))
	powers.append(0)
	vertices.append(list())
	i = i + 1
i = 0
lim = n - 1
while i < lim:
	edge = input()
	edge = edge.split()
	edge[0] = int(edge[0]) - 1
	edge[1] = int(edge[1]) - 1
	vertices[edge[0]].append(edge[1])
	vertices[edge[1]].append(edge[0])
	powers[edge[0]] = powers[edge[0]] + 1
	powers[edge[1]] = powers[edge[1]] + 1
	i = i + 1
possibility = True
i = 0
while i < n:
	if powers[i] > 2 or powers[i] == 0:
		possibility = False
		break
	i = i + 1
if possibility == False:
	print(-1)
else:
	tree = list()
	i = 0
	while i < n:
		tree.append(None)
		i = i + 1
	i = 0
	while i < n:
		if powers[i] == 1:
			tree[0] = i
			tree[1] = vertices[i][0]
			break
		i = i + 1
	i = 1
	lim = n - 1
	while i < lim:
		if vertices[tree[i]][0] != tree[i - 1]:
			tree[i + 1] = vertices[tree[i]][0]
		else:
			tree[i + 1] = vertices[tree[i]][1]
		i = i + 1
	min = -1
	right_cache = list()
	amount = 0
	cache = list()
	i = 0
	while i < n:
		cache.append(None)
		i = i + 1
	i = 0
	while i < 3:
		j = 0
		while j < 3:
			if j == i:
				j = j + 1
				continue
			cache[tree[0]] = i
			cache[tree[1]] = j
			amount = costs[tree[0]][i] + costs[tree[1]][j]
			prev_colors = list()
			prev_colors.append(i)
			prev_colors.append(j)
			k = 2
			while k < n:
				cur_color = 3 - prev_colors[0] - prev_colors[1]
				cache[tree[k]] = cur_color
				amount = amount + costs[tree[k]][cur_color]
				prev_colors[0] = prev_colors[1]
				prev_colors[1] = cur_color
				k = k + 1
			if min == -1:
				min = amount
				right_cache = cache.copy()
			elif amount < min:
				min = amount
				right_cache = cache.copy()
			j = j + 1
		i = i + 1
	print(min)
	i = 0
	while i < n:
		print(right_cache[i] + 1, end=' ')
		i = i + 1


n = int(input())
color = []
for i in range(3):
	color.append(list(map(int, input().split())))
graph = {}
degree = {}
color_assign = {}
for i in range(1, n + 1):
	graph[i] = []
	degree[i] = 0
	color_assign[i] = -1
flag = 0
for i in range(n - 1):
	(a, b) = map(int, input().split())
	degree[a] += 1
	degree[b] += 1
	graph[a].append(b)
	graph[b].append(a)
	if degree[a] > 2 or degree[b] > 2:
		flag = 1
		break
if flag == 1:
	print(-1)
else:
	starting_node = -1
	for keys in degree:
		if degree[keys] == 1:
			starting_node = keys
			break
	sumo = float('inf')
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			for k in range(3):
				if j == k or i == k:
					continue
				else:
					s1 = 0
					first = starting_node
					second = graph[first][0]
					third = graph[second][0]
					if graph[second][0] == first:
						third = graph[second][1]
					count = 1
					temp_color = {}
					while count <= n // 3:
						s1 += color[i][first - 1] + color[j][second - 1] + color[k][third - 1]
						temp_color[first] = i + 1
						temp_color[second] = j + 1
						temp_color[third] = k + 1
						if count == n // 3:
							break
						first = graph[third][0]
						if second == first:
							first = graph[third][1]
						second = graph[first][0]
						if second == third:
							second = graph[first][1]
						third = graph[second][0]
						if third == first:
							third = graph[second][1]
						count += 1
					if n % 3 == 1:
						first = graph[third][0]
						if second == first:
							first = graph[third][1]
						s1 += color[i][first - 1]
						temp_color[first] = i + 1
					if n % 3 == 2:
						first = graph[third][0]
						if second == first:
							first = graph[third][1]
						second = graph[first][0]
						if second == third:
							second = graph[first][1]
						s1 += color[i][first - 1] + color[j][second - 1]
						temp_color[first] = i + 1
						temp_color[second] = j + 1
					if s1 < sumo:
						sumo = s1
						for keys in color_assign:
							color_assign[keys] = temp_color[keys]
	print(sumo)
	for keys in color_assign:
		print(color_assign[keys], end=' ')


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	n = int(input())
	ar = []
	for i in range(3):
		ar.append(list(map(int, input().split())))
	graph = defaultdict(list)
	deg = [0] * n
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
		deg[a - 1] += 1
		deg[b - 1] += 1
	if max(deg) > 2:
		print(-1)
		sys.exit(0)

	def DFS(v, visited, cur):
		visited[v] = True
		if paint[v] == 0:
			paint[v] = 6 - cur[-1] - cur[-2]
			if len(cur) == 3:
				cur = cur[1:]
		cur.append(paint[v])
		for i in graph[v]:
			if visited[i] == False:
				DFS(i, visited, cur + [])
		return paint
	au = []
	au.append([1, 2, 3])
	au.append([2, 3, 1])
	au.append([2, 1, 3])
	au.append([3, 1, 2])
	au.append([3, 2, 1])
	au.append([1, 3, 2])
	mi = 9999999999999999999999999
	tot = []
	for i in range(6):
		paint = [0] * n
		visited = [False] * n
		paint[0] = au[i][2]
		t = 0
		for j in graph[0]:
			paint[j] = au[i][t]
			t += 1
		paint = DFS(0, visited, [])
		ans = 0
		for i in range(n):
			ans += ar[paint[i] - 1][i]
		if ans < mi:
			mi = ans
			tot = paint
	print(mi)
	print(*tot, sep=' ')
t = threading.Thread(target=main)
t.start()
t.join()


import sys
input = sys.stdin.readline
n = int(input())
cost = [tuple(map(int, input().split())) for _ in range(3)]
adj_list = [[] for _ in range(n)]
for _ in range(n - 1):
	(ui, vi) = map(int, input().split())
	adj_list[ui - 1].append(vi - 1)
	adj_list[vi - 1].append(ui - 1)
for i in range(n):
	if len(adj_list[i]) >= 3:
		print(-1)
		exit()
	if len(adj_list[i]) == 1:
		root = i
nodes = [root]
prev = None
for i in range(n - 1):
	for nn in adj_list[nodes[-1]]:
		if nn != prev:
			nodes.append(nn)
	prev = nodes[-2]
ans_cost = 10 ** 18
ans_l = None
for (c0, c1) in [(0, 1), (1, 0), (1, 2), (2, 1), (2, 0), (0, 2)]:
	cost_cand = 0
	color = [-1] * n
	color[nodes[0]] = c0
	color[nodes[1]] = c1
	cost_cand += cost[c0][nodes[0]] + cost[c1][nodes[1]]
	for i in range(2, n):
		s = set([color[nodes[i - 2]], color[nodes[i - 1]]])
		if s == {0, 1}:
			color[nodes[i]] = 2
			cost_cand += cost[2][nodes[i]]
		elif s == {1, 2}:
			color[nodes[i]] = 0
			cost_cand += cost[0][nodes[i]]
		if s == {2, 0}:
			color[nodes[i]] = 1
			cost_cand += cost[1][nodes[i]]
	if ans_cost > cost_cand:
		ans_cost = cost_cand
		ans_l = color
print(ans_cost)
for ans_li in ans_l[:-1]:
	print(ans_li + 1, end=' ')
print(ans_l[-1] + 1)


from collections import defaultdict as dd
n = int(input())
r = list(map(int, input().split()))
b = list(map(int, input().split()))
g = list(map(int, input().split()))
d = dd(list)
ll = [r, b, g]
l = [0] * (n + 1)
alp = []
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
	l[u] += 1
	l[v] += 1
cou = 0
if max(l) > 2:
	print(-1)
else:
	for i in range(len(l)):
		if l[i] == 1:
			ind = i
			break
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			for k in range(3):
				if k == i or k == j:
					continue
				a = ind
				aa = i
				bb = j
				cc = k
				li = []
				res = 0
				s = []
				vis = [0] * (n + 1)
				res += ll[aa][a - 1]
				li.append((a, aa + 1))
				vis[a] = 1
				for v in d[a]:
					if vis[v] == 0:
						na = v
				vis[a] = 1
				a = na
				res += ll[bb][a - 1]
				li.append((a, bb + 1))
				for v in d[a]:
					if vis[v] == 0:
						na = v
				vis[a] = 1
				a = na
				vis[a] = 1
				s.append(a)
				cou += 1
				aa = cc
				while s:
					a = s.pop()
					res += ll[aa][a - 1]
					li.append((a, aa + 1))
					vis[a] = 1
					for v in d[a]:
						if vis[v] == 0:
							s.append(v)
					for v in range(3):
						if v != bb and v != cc:
							aa = v
					bb = cc
					cc = aa
			alp.append((res, li))
	alp.sort()
	print(alp[0][0])
	alp[0][1].sort()
	for i in alp[0][1]:
		print(i[1], end=' ')


from math import inf
import statistics
import itertools

def min_tree_paint(v, graph, colors):
	start = graph.index(min(graph, key=lambda z: len(z)))
	combs = list(itertools.permutations([0, 1, 2]))
	for k in graph:
		if len(k) >= 3:
			print('-1')
			return
	min_cost = inf
	min_path = dict()
	for c in combs:
		x = start
		count = 0
		cost = 0
		path = dict()
		last_x = -1
		while True:
			chosen = c[count % 3]
			cost += colors[chosen][x]
			path[x] = chosen
			if count != 0 and len(graph[x]) == 1:
				break
			for y in graph[x]:
				if y != last_x:
					last_x = x
					x = y
					break
			count += 1
		if cost < min_cost:
			min_path = path.copy()
			min_cost = cost
	print(min_cost)
	for x in range(v):
		print(min_path[x] + 1, end=' ')
	print()
v = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
colors = [c1, c2, c3]
graph = [[] for _ in range(v)]
for _ in range(v - 1):
	arr = list(map(int, input().split()))
	graph[arr[0] - 1].append(arr[1] - 1)
	graph[arr[1] - 1].append(arr[0] - 1)
min_tree_paint(v, graph, colors)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

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

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def bfs(g, st, col):
	global c1, c2, c3, currnas
	dist = [-1] * len(g)
	dist[st] = 0
	par = [-1] * len(g)
	queue = deque([])
	queue.append(st)
	while len(queue) != 0:
		s = queue.popleft()
		if dist[s] > 1:
			p1 = col[par[s]]
			p2 = col[par[par[s]]]
			temp = 6 - (p1 + p2)
			if temp == 1:
				currnas += c1[s]
			if temp == 2:
				currnas += c2[s]
			if temp == 3:
				currnas += c3[s]
			col[s] = temp
		for i in g[s]:
			if dist[i] == -1:
				par[i] = s
				dist[i] = dist[s] + 1
				queue.append(i)

def solve(case):
	n = int(inp())
	global c1, c2, c3, currnas, ed
	c1 = lis()
	c2 = lis()
	c3 = lis()
	ed = (-1, -1)
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = sep()
		a -= 1
		b -= 1
		if ed == (-1, -1):
			ed = (a, b)
		g[a].append(b)
		g[b].append(a)
	for i in range(n):
		if len(g[i]) > 2:
			print(-1)
			return
	ans = inf
	colans = [0] * n
	currnas = c1[0]
	col = [0] * n
	col[0] = 1
	curr = 2
	for i in g[0]:
		if curr == 2:
			currnas += c2[i]
			col[i] = curr
			curr = 3
		else:
			currnas += c3[i]
			col[i] = curr
			curr = 2
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	currnas = c1[0]
	col = [0] * n
	col[0] = 1
	curr = 3
	for i in g[0]:
		if curr == 3:
			currnas += c3[i]
			col[i] = curr
			curr = 2
		else:
			currnas += c2[i]
			col[i] = curr
			curr = 3
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	currnas = c2[0]
	col = [0] * n
	col[0] = 2
	curr = 1
	for i in g[0]:
		if curr == 1:
			currnas += c1[i]
			col[i] = curr
			curr = 3
		else:
			currnas += c3[i]
			col[i] = curr
			curr = 1
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	currnas = c2[0]
	col = [0] * n
	col[0] = 2
	curr = 3
	for i in g[0]:
		if curr == 3:
			currnas += c3[i]
			col[i] = curr
			curr = 1
		else:
			currnas += c1[i]
			col[i] = curr
			curr = 3
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	currnas = c3[0]
	col = [0] * n
	col[0] = 3
	curr = 1
	for i in g[0]:
		if curr == 1:
			currnas += c1[i]
			col[i] = curr
			curr = 2
		else:
			currnas += c2[i]
			col[i] = curr
			curr = 1
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	currnas = c3[0]
	col = [0] * n
	col[0] = 3
	curr = 2
	for i in g[0]:
		if curr == 2:
			currnas += c2[i]
			col[i] = curr
			curr = 1
		else:
			currnas += c1[i]
			col[i] = curr
			curr = 2
	bfs(g, 0, col)
	if ans > currnas:
		ans = currnas
		colans = deepcopy(col)
	print(ans)
	print(' '.join((str(colans[i]) for i in range(n))))
ed = (-1, -1)
(c1, c2, c3) = ([], [], [])
currnas = 0
testcase(1)


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)
		exit(0)
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=' ')


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 sys
n = int(input())
c1 = [int(i) for i in input().split()]
c2 = [int(i) for i in input().split()]
c3 = [int(i) for i in input().split()]
ccc = [c1, c2, c3]
cnt = [0] * (n + 1)
neigh = [[] for i in range(n + 1)]
for j in range(n - 1):
	(a, b) = [int(i) for i in sys.stdin.readline().split()]
	cnt[a] += 1
	cnt[b] += 1
	neigh[a].append(b)
	neigh[b].append(a)
leaf = -1
for i in range(1, n + 1):
	if cnt[i] == 1:
		leaf = i
	elif cnt[i] > 2:
		print(-1)
		exit()
color = [-1] * (n + 1)
v = leaf
cc = 0
for i in range(n):
	color[v] = cc
	cc = (cc + 1) % 3
	ne = neigh[v]
	if color[ne[0]] == -1:
		v = ne[0]
	elif len(ne) > 1:
		v = ne[1]
mn = sum(c1) + sum(c2) + sum(c3)
ch = [(0, 1, 2), (0, 2, 1), (1, 2, 0), (1, 0, 2), (2, 0, 1), (2, 1, 0)]
mni = -1
for i in range(6):
	pt = ch[i]
	cost = 0
	for v in range(1, n + 1):
		rc = pt[color[v]]
		cost += ccc[rc][v - 1]
	if cost < mn:
		mni = i
		mn = cost
print(mn)
pt = ch[mni]
ans = []
for v in range(1, n + 1):
	rc = pt[color[v]]
	ans.append(rc + 1)
print(*ans)


import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline().split()[0])
c = []
c.append([int(x) for x in readline().split()])
c.append([int(x) for x in readline().split()])
c.append([int(x) for x in readline().split()])
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, readline().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
ans = True
sv = 0
for i in range(n):
	if len(g[i]) > 2:
		ans = False
	if len(g[i]) == 1:
		sv = i

def bfs(v1, v2):
	nv = g[sv][0]
	tmp = [_ for _ in range(n)]
	tmp[sv] = v1
	tmp[nv] = v2
	cost = c[v1][sv] + c[v2][nv]
	lv = sv
	v3 = 3 - v1 - v2
	v = [v1, v2, v3]
	count = 2
	while True:
		if len(g[nv]) == 1:
			break
		if lv == g[nv][0]:
			lv = nv
			nv = g[nv][1]
		else:
			lv = nv
			nv = g[nv][0]
		cost += c[v[count]][nv]
		tmp[nv] = v[count]
		count += 1
		count %= 3
	return [cost, tmp]
if ans and n != 1:
	min_cost = pow(10, 15)
	v1 = 0
	v2 = 0
	tmp = []
	for i in range(3):
		for j in range(2):
			cost = bfs(i, (i + 1 + j) % 3)
			if cost[0] < min_cost:
				min_cost = cost[0]
				v1 = i
				v2 = (i + 1 + j) % 3
				tmp = cost[1]
	print(min_cost)
	for i in range(n):
		print(tmp[i] + 1, end=' ')
elif n == 1:
	print(min(c[0][0], c[1][0], c[2][0]))
else:
	print(-1)


import sys
n = int(input())
costs = [list(map(int, input().split())) for _ in range(3)]
deg = [0] * n
adj = [[] for _ in range(n)]
for (u, v) in (map(int, l.split()) for l in sys.stdin):
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
	deg[u - 1] += 1
	deg[v - 1] += 1
if max(deg) > 2:
	print(-1)
	exit()
s = deg.index(1)
t = deg.index(1, s + 1)
inf = 10 ** 18
dp = [[[inf] * 3 for _ in range(3)] for _ in range(n + 1)]
for i in range(3):
	for j in range(3):
		dp[n][i][j] = 0
(v, child) = (t, n)
childs = [-1] * n
while True:
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			for k in range(3):
				if i == k or j == k:
					continue
				dp[v][i][j] = min(dp[v][i][j], dp[child][j][k] + costs[i][v])
	for dest in adj[v]:
		if dest == child:
			continue
		child = v
		v = dest
		childs[v] = child
		break
	else:
		break
color = [0] * n
ans = inf
(x, y) = (0, 0)
for i in range(3):
	for j in range(3):
		if ans > dp[s][i][j]:
			ans = dp[s][i][j]
			(x, y) = (i, j)
v = s
while v != -1:
	color[v] = x + 1
	for z in range(3):
		if x != z and y != z:
			(x, y) = (y, z)
			v = childs[v]
			break
print(ans)
print(*color)


n = int(input())
c = []
c.append([int(x) for x in input().split()])
c.append([int(x) for x in input().split()])
c.append([int(x) for x in input().split()])
ngbr = {}
flag = 1
for i in range(n - 1):
	(i, j) = [int(x) for x in input().split()]
	if i not in ngbr:
		ngbr[i] = [j]
	else:
		ngbr[i].append(j)
	if j not in ngbr:
		ngbr[j] = [i]
	else:
		ngbr[j].append(i)
	if len(ngbr[i]) > 2 or len(ngbr[j]) > 2:
		flag = 0
if not flag:
	print(-1)
else:
	right_order = []
	for el in ngbr:
		if len(ngbr[el]) == 1:
			cur = el
			break
	nex = ngbr[cur][0]
	while len(ngbr[nex]) != 1:
		right_order.append(cur)
		for nex2 in ngbr[nex]:
			if nex2 != cur:
				break
		cur = nex
		nex = nex2
	right_order.extend([ngbr[nex][0], nex])
	sum = [[0 for i in range(3)] for j in range(3)]
	for i in range(3):
		for j in range(3):
			for el in right_order[i::3]:
				sum[i][j] += c[j][el - 1]
	min_sum = sum[0][0] + sum[1][1] + sum[2][2]
	right_colors = [0, 1, 2]
	for i in set(range(3)):
		for j in set(range(3)) - {i}:
			for k in set(range(3)) - {i} - {j}:
				if sum[0][i] + sum[1][j] + sum[2][k] < min_sum:
					min_sum = sum[0][i] + sum[1][j] + sum[2][k]
					right_colors = [i, j, k]
	print(min_sum)
	result_color = [0 for i in range(n)]
	for i in range(len(right_order)):
		result_color[right_order[i] - 1] = right_colors[i % 3]
	for i in result_color:
		print(i + 1, end=' ')
	print()


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)
	sys.exit()
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=' ')


import sys
import math

def get_colour(s, i, cur_node, a, b, c):
	id_x = i % 3
	char = s[id_x]
	if char == 'a':
		return (a[cur_node - 1], 1)
	if char == 'b':
		return (b[cur_node - 1], 2)
	if char == 'c':
		return (c[cur_node - 1], 3)
	return -1
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
e = [set() for u in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	e[u].add(v)
	e[v].add(u)
for i in range(1, n + 1):
	if len(e[i]) > 2 or len(e[i]) == 0:
		print(-1)
		exit()
start_node = 1
for i in range(1, n + 1):
	if len(e[i]) == 1:
		start_node = i
		break
min_cost = 10 ** 16
s_list = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
result_color_map = None
for s in s_list:
	cur_cost = 0
	color_map = [0] * (n + 1)
	blaa_map = [0] * (n + 1)
	cur_node = start_node
	i = 0
	while True:
		if color_map[cur_node] > 0:
			break
		colour_cost = get_colour(s, i, cur_node, a, b, c)
		cur_cost += colour_cost[0]
		color_map[cur_node] = colour_cost[1]
		blaa_map[cur_node] = colour_cost[0]
		i += 1
		for next_node in e[cur_node]:
			if color_map[next_node] == 0:
				cur_node = next_node
				break
	if cur_cost < min_cost:
		min_cost = cur_cost
		result_color_map = color_map
print(min_cost)
for i in result_color_map[1:]:
	print(i, end=' ')


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()


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) = 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 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)))
main()


from collections import defaultdict as dd
n = int(input())
firs = list(map(int, input().split()))
sec = list(map(int, input().split()))
third = list(map(int, input().split()))
graph = dd(list)
c = list(zip(firs, sec, third))
for i in range(n - 1):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	graph[x] += [y]
	graph[y] += [x]
flag = 0
for i in graph:
	if len(graph[i]) > 2:
		flag = 1
		break
if flag:
	print(-1)
else:
	for k in graph:
		if len(graph[k]) == 1:
			start = k
			break
	l = []
	path = []
	path2 = []
	for i in range(3):
		for j in range(3):
			if i != j:
				befbef = i
				bef = j
				k = 3 - i - j
				path = [[start, befbef + 1]]
				cost = c[start][befbef]
				visited = dict()
				visited[start] = 1
				now = start
				for p in range(n - 1):
					(befbef, bef, k) = (bef, k, befbef)
					for g in graph[now]:
						if g not in visited:
							now = g
							visited[now] = 1
					cost += c[now][befbef]
					path += [[now, befbef + 1]]
				path2 += [path]
				l += [cost]
	print(min(l))
	for i in range(len(l)):
		if l[i] == min(l):
			ans = i
			break
	x = path2[ans]
	ans = [0] * n
	for i in x:
		ans[i[0]] = i[1]
	print(*ans)


import math
import itertools

def Solve():
	tree = dict()
	n = int(input())
	cost1 = list(map(int, input().split()))
	cost2 = list(map(int, input().split()))
	cost3 = list(map(int, input().split()))
	costs = [(cost1[i], cost2[i], cost3[i]) for i in range(len(cost1))]
	no_three_color = False
	for i in range(n - 1):
		(a, b) = 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_three_color = True
		if len(tree[b]) > 2:
			no_three_color = True
	if no_three_color:
		print(-1)
		return
	for node in 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))
	index_permutation = -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]
		if cost_sum < min_sum:
			min_sum = cost_sum
			index_permutation = permut
	sol = [0] * (len(lst) + 1)
	index = 0
	permt = permutations[index_permutation]
	for i in lst:
		sol[i] = permt[index % 3]
		index += 1
	solution = sol[1:]
	print(min_sum)
	print(*solution)
Solve()


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]
graph = [[] for i in range(n)]
for i in range(n - 1):
	(v1, v2) = map(int, input().split())
	graph[v1 - 1].append(v2 - 1)
	graph[v2 - 1].append(v1 - 1)
for i in range(n):
	if len(graph[i]) > 2:
		print(-1)
		break
else:
	for start in range(n):
		if len(graph[start]) == 1:
			ans = 10 ** 18
			anscol = []
			for col in range(3):
				v = start
				used = [0] * n
				used[v] = 1
				colors = [0] * n
				colors[v] = col + 1
				cost = c[col][v]
				col = (col + 1) % 3
				for i in range(n - 1):
					if not used[graph[v][0]]:
						v = graph[v][0]
					elif not used[graph[v][1]]:
						v = graph[v][1]
					used[v] = 1
					cost += c[col][v]
					colors[v] = col + 1
					col = (col + 1) % 3
				if cost < ans:
					ans = cost
					anscol = colors[:]
				v = start
				used = [0] * n
				used[v] = 1
				colors = [0] * n
				colors[v] = col + 1
				cost = c[col][v]
				col = (col - 1) % 3
				for i in range(n - 1):
					if not used[graph[v][0]]:
						v = graph[v][0]
					elif not used[graph[v][1]]:
						v = graph[v][1]
					used[v] = 1
					cost += c[col][v]
					colors[v] = col + 1
					col = (col - 1) % 3
				if cost < ans:
					ans = cost
					anscol = colors[:]
			print(ans)
			print(*anscol)
			break
	else:
		print(-1)


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)
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]
	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
	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
	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
	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
	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
	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)


from sys import stdin
from array import array
input = stdin.readline
n = int(input())
costs = [array('L', (int(i) for i in input().split())) for x in range(3)]
d = [[] for i in range(n)]
answer = array('b', (0 for i in range(n)))
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	d[u - 1].append(v - 1)
	d[v - 1].append(u - 1)
	if len(d[u - 1]) > 2 or len(d[v - 1]) > 2:
		print(-1)
		exit(0)
g = [e for (e, f) in enumerate(d) if len(f) == 1][0]
choice = 0
codes = [(0, 1, 2), (0, 2, 1), (1, 2, 0), (1, 0, 2), (2, 1, 0), (2, 0, 1)]
vals = [0, 0, 0, 0, 0, 0]
node = g
prevnode = None
for index in range(n):
	vals = [base + costs[codes[i][choice]][node] for (i, base) in enumerate(vals)]
	choice = (choice + 1) % 3
	if index == n - 1:
		break
	(prevnode, node) = (node, d[node][0]) if len(d[node]) == 1 else (node, d[node][1]) if d[node][0] == prevnode else (node, d[node][0])
print(min(vals))
for (i, val) in enumerate(vals):
	if val == min(vals):
		answer = array('b', (0 for i in range(n)))
		node = g
		prevnode = None
		choice = 0
		for index in range(n):
			answer[node] = codes[i][choice] + 1
			choice = (choice + 1) % 3
			if index == n - 1:
				break
			(prevnode, node) = (node, d[node][0]) if len(d[node]) == 1 else (node, d[node][1]) if d[node][0] == prevnode else (node, d[node][0])
		break
print(*answer)


import sys
import math
input = sys.stdin.readline
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def s(root, d, out, c1, c2, c3):
	v = [0] * n
	v[root - 1] = 1
	out[root - 1] = c1[-1]
	q = [c1, c2, c3]
	p = 1
	cost = c1[root - 1]
	node = root
	while True:
		if len(d[node]) == 1 and node != root:
			break
		for i in d[node]:
			if v[i - 1] == 0:
				v[i - 1] = 1
				cost += q[p % 3][i - 1]
				out[i - 1] = q[p % 3][-1]
				p += 1
				node = i
				break
	return cost
n = inp()
d = {}
for i in range(n):
	d[i + 1] = []
r = inlt()
g = inlt()
b = inlt()
r.append(1)
b.append(3)
g.append(2)
for i in range(n - 1):
	(x, y) = invr()
	d[x].append(y)
	d[y].append(x)
f = 0
for i in d:
	if len(d[i]) > 2:
		print(-1)
		f = 1
		exit()
root = []
for i in range(n):
	if len(d[i + 1]) == 1:
		root = i + 1
		break
out = [0] * n
cost = []
q = [r, g, b]
for i in range(3):
	for j in range(3):
		if i != j:
			cost.append([s(root, d, out, q[i], q[j], q[3 - i - j]), i, j])
minindex = 0
for i in range(6):
	if cost[minindex][0] > cost[i][0]:
		minindex = i
i = cost[minindex][1]
j = cost[minindex][2]
cost = s(root, d, out, q[i], q[j], q[3 - i - j])
print(cost)
print(*out)


from itertools import product, combinations
from math import sqrt

def count(tree, c_first, c_second, c_third, n, color_list):
	ans = 0
	for i in range(n):
		if i % 3 == 0:
			ans += color_list[c_first - 1][tree[i] - 1]
		elif i % 3 == 1:
			ans += color_list[c_second - 1][tree[i] - 1]
		else:
			ans += color_list[c_third - 1][tree[i] - 1]
	return ans
n = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
D = dict()
for i in range(1, n + 1):
	D[i] = set()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	D[u].add(v)
	D[v].add(u)
ans = True
for el in D:
	if len(D[el]) >= 3:
		ans = False
		break
if ans:
	tree = []
	for el in D:
		if len(D[el]) == 1:
			tree.append(el)
			break
	nv = list(D[tree[0]])[0]
	while len(D[nv]) == 2:
		tree.append(nv)
		D[nv].discard(tree[-2])
		nv = list(D[nv])[0]
	tree.append(nv)
	color_list = [c1, c2, c3]
	colors = dict()
	for i in range(1, n + 1):
		colors[i] = 0
	ans = count(tree, 1, 2, 3, n, color_list)
	(x1, x2, x3) = (1, 2, 3)
	for (c_first, c_second, c_third) in product(range(1, 4), repeat=3):
		if c_first == c_second or c_first == c_third or c_second == c_third:
			continue
		maybe = count(tree, c_first, c_second, c_third, n, color_list)
		if ans > maybe:
			ans = maybe
			(x1, x2, x3) = (c_first, c_second, c_third)
	print(ans)
	for i in range(n):
		if i % 3 == 0:
			colors[tree[i]] = x1
		elif i % 3 == 1:
			colors[tree[i]] = x2
		else:
			colors[tree[i]] = x3
	for i in range(1, n + 1):
		print(colors[i], end=' ')
	print()
else:
	print(-1)


import sys
sys.setrecursionlimit(10 ** 9)
maxi = 0

def rint():
	return map(int, sys.stdin.readline().split())

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

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

def bfs(a):
	global maxi
	bool[a] = True
	queue = [a]
	level = [0] * (n + 1)
	level[a] = 0
	leveli[0].append(a)
	while queue:
		z = queue.pop(0)
		for i in hash[z]:
			if not bool[i]:
				bool[i] = True
				queue.append(i)
				level[i] = level[z] + 1
				leveli[level[i]].append(i)
				maxi = max(level[i], maxi)
n = oint()
c = []
for i in range(3):
	c.append(list(rint()))
(l1, l2, l3) = c
hash = []
for i in range(n + 1):
	hash.append([])
bool = [False] * (n + 1)
leveli = []
for i in range(n):
	leveli.append([])
for i in range(n - 1):
	(a, b) = map(int, input().split())
	hash[a].append(b)
	hash[b].append(a)
perm = [[0, 1, 2], [1, 0, 2], [1, 2, 0], [2, 1, 0], [2, 0, 1], [0, 2, 1]]
count = 0
s = -1
for i in range(1, n + 1):
	if len(hash[i]) == 1:
		s = i
		break
if s == -1:
	print(-1)
	exit()
bfs(s)
level = 0
mini = 10 ** 18
for i in range(len(leveli)):
	if len(leveli[i]) > 1:
		print(-1)
		exit()
yo = 0
for i in range(len(perm)):
	level = 0
	count = 0
	cost = 0
	while level <= maxi:
		count = count % 3
		for j in leveli[level]:
			z = perm[i][count]
			if z == 0:
				cost += l1[j - 1]
			elif z == 1:
				cost += l2[j - 1]
			else:
				cost += l3[j - 1]
		level += 1
		count += 1
	if cost < mini:
		yo = i
		mini = cost
level = 0
count = 0
cost = 0
ans = [0] * n
while level <= maxi:
	count = count % 3
	for j in leveli[level]:
		z = perm[yo][count]
		ans[j - 1] = z + 1
	level += 1
	count += 1
print(mini)
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]
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)
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]
maxi = 10 ** 9 * n + 5
ans = 0
i = 1
for j in range(6):
	sumi = 0
	for i in range(1, n + 1):
		sumi += a[g[j][i]][i - 1]
	if maxi > sumi:
		maxi = sumi
		ans = j
print(maxi)
print(*g[ans][1:])


import sys, os, io
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(curr, a, b, c):
	q = deque()
	q.append(curr)
	cost = [0] * n
	dist = [0] * n
	vis = [0] * n
	color = [0] * n
	vis[curr] = 1
	color[curr] = 1
	cost[curr] = a[curr]
	while len(q):
		curr = q.popleft()
		for i in graph[curr]:
			if vis[i] == 0:
				vis[i] = 1
				dist[i] = dist[curr] + 1
				q.append(i)
				if dist[i] % 3 == 0:
					cost[i] = a[i]
					color[i] = 1
				elif dist[i] % 3 == 1:
					cost[i] = b[i]
					color[i] = 2
				else:
					cost[i] = c[i]
					color[i] = 3
	if len(faltu) == 0:
		return sum(cost)
	else:
		dic = {}
		dic[1] = 1
		dic[2] = 2
		dic[3] = 3
		if faltu[0] == 2:
			dic[1] = 2
			dic[2] = 3
			dic[3] = 1
		elif faltu[0] == 3:
			dic[1] = 1
			dic[2] = 3
			dic[3] = 2
		elif faltu[0] == 4:
			dic[1] = 2
			dic[2] = 1
			dic[3] = 3
		elif faltu[0] == 5:
			dic[1] = 3
			dic[2] = 2
			dic[3] = 1
		elif faltu[0] == 6:
			dic[1] = 3
			dic[2] = 1
			dic[3] = 2
		for i in color:
			print(dic[i], end=' ')
		print()
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
graph = [[] for i in range(n)]
for i in range(n - 1):
	(ui, vi) = [int(i) - 1 for i in input().split()]
	graph[ui].append(vi)
	graph[vi].append(ui)
okk = 0
ind = 0
j = 0
for i in graph:
	if len(i) > 2:
		print(-1)
		exit()
	if len(i) == 1:
		ind = j
		okk = 1
	j += 1
if okk == 0 and n % 3:
	print(-1)
	exit()
faltu = []
a1 = bfs(ind, a, b, c)
a2 = bfs(ind, b, c, a)
a3 = bfs(ind, a, c, b)
a4 = bfs(ind, b, a, c)
a5 = bfs(ind, c, b, a)
a6 = bfs(ind, c, a, b)
ans = min(a1, a2, a3, a4, a5, a6)
faltu = []
print(ans)
if ans == a1:
	faltu = [1]
	bfs(ind, a, b, c)
elif ans == a2:
	faltu = [2]
	bfs(ind, b, c, a)
elif ans == a3:
	faltu = [3]
	bfs(ind, a, c, b)
elif ans == a4:
	faltu = [4]
	bfs(ind, b, a, c)
elif ans == a5:
	faltu = [5]
	bfs(ind, c, b, a)
elif ans == a6:
	faltu = [6]
	bfs(ind, c, a, b)


from pprint import pprint
from itertools import permutations

def node_color_cost(color_cost, node_id):
	return (color_cost[0][node_id], color_cost[1][node_id], color_cost[2][node_id])

def read_edges(N):
	edges = []
	for _ in range(N - 1):
		(n1, n2) = map(int, input().split())
		if n1 > n2:
			(n1, n2) = (n2, n1)
		edges.append((n1, n2))
	edges.sort()
	return edges

def min_cost_for_list(edges):
	global_min_cost = -1
	start_node = 0
	for color_cost in range(0, 3):
		cost = 0

def main():
	N = int(input())
	color_cost = []
	for _ in range(3):
		color_cost.append([0] + list(map(int, input().split())))
	nodes = [None] * (N + 1)
	for _ in range(N - 1):
		(n1, n2) = map(int, input().split())
		if nodes[n1] is None:
			nodes[n1] = []
		if nodes[n2] is None:
			nodes[n2] = []
		nodes[n1].append(n2)
		nodes[n2].append(n1)
		if len(nodes[n1]) > 2 or len(nodes[n2]) > 2:
			print(-1)
			return None
	cur_node = 0
	for i in range(1, N + 1):
		if len(nodes[i]) == 1:
			cur_node = i
			break
	color_combination = list(permutations([0, 1, 2]))
	cost = [0] * len(color_combination)
	color_path = []
	for i in range(len(color_combination)):
		color_path.append([0] * (N + 1))
	prev_node = 0
	i = 0
	while True:
		for (j, comb) in enumerate(color_combination):
			cost[j] += color_cost[color_combination[j][i % 3]][cur_node]
			color_path[j][cur_node] = color_combination[j][i % 3] + 1
		if len(nodes[cur_node]) > 1 or prev_node == 0:
			for n in nodes[cur_node]:
				if n != prev_node:
					(prev_node, cur_node) = (cur_node, n)
					break
		else:
			break
		i += 1
	index_min = min(range(len(cost)), key=cost.__getitem__)
	print(cost[index_min])
	for i in range(1, len(color_path[index_min])):
		print(color_path[index_min][i], end=' ')
	print()
main()


def dfs(colors, leaf, edges):
	stack = [edges[leaf][0]]
	visited = set()
	n = len(edges)
	visited.add(leaf)
	used = {}
	for i in range(1, n + 1):
		used[i] = []
	used[edges[leaf][0]].append(colors[leaf])
	used[edges[leaf][0]].append(colors[edges[leaf][0]])
	while stack:
		curr = stack.pop()
		if curr not in visited:
			visited.add(curr)
			for kid in edges[curr]:
				if kid not in visited:
					stack.append(kid)
					poss = [1, 2, 3]
					for i in used[curr]:
						poss.remove(i)
					colors[kid] = poss[0]
					used[kid].append(colors[kid])
					used[kid].append(colors[curr])

def cost(colors, color1, color2, color3):
	c = 0
	colors.pop(0)
	n = len(colors)
	for i in range(n):
		if colors[i] == 1:
			c += color1[i]
		elif colors[i] == 2:
			c += color2[i]
		else:
			c += color3[i]
	return c

def solve(edges, leaf, color1, color2, color3):
	min_cost = float('inf')
	perms = [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
	n = len(edges)
	ans = []
	for i in perms:
		colors = [0] * (n + 1)
		colors[leaf] = i[0]
		colors[edges[leaf][0]] = i[1]
		dfs(colors, leaf, edges)
		c = cost(colors, color1, color2, color3)
		if c < min_cost:
			min_cost = c
			ans = colors[:]
	print(min_cost)
	for i in ans:
		print(i, end=' ')

def main():
	n = int(input())
	color1 = list(map(int, input().split()))
	color2 = list(map(int, input().split()))
	color3 = list(map(int, input().split()))
	edges = {}
	for i in range(1, n + 1):
		edges[i] = []
	found = True
	leaf = -1
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		edges[a].append(b)
		edges[b].append(a)
		if len(edges[a]) > 2:
			found = False
		if len(edges[b]) > 2:
			found = False
	if not found:
		print(-1)
		return
	for i in range(1, n + 1):
		if len(edges[i]) == 1:
			leaf = i
			break
	solve(edges, leaf, color1, color2, color3)
main()


def main():
	n = int(input())
	costs = [list(map(int, input().split(' '))), list(map(int, input().split(' '))), list(map(int, input().split(' ')))]
	nodes = []
	for i in range(0, n):
		nodes.append([])
	for i in range(0, n - 1):
		(node_1_index, node_2_index) = map(int, input().split(' '))
		nodes[node_1_index - 1].append(node_2_index - 1)
		nodes[node_2_index - 1].append(node_1_index - 1)
	for node in nodes:
		if len(node) > 2:
			print(-1)
			return
	init_node_index = -1
	for i in range(0, n):
		if len(nodes[i]) == 1:
			init_node_index = i
			break
	minimum_node_colors = []
	minimum_cost = -1
	for i in range(0, 3):
		for j in range(0, 3):
			if i == j:
				continue
			nodes_colors = [0] * n
			prev_node_index = init_node_index
			nodes_colors[prev_node_index] = i
			current_node_index = nodes[prev_node_index][0]
			nodes_colors[current_node_index] = j
			while True:
				next_node_index = get_next_node(prev_node_index, nodes[current_node_index])
				nodes_colors[next_node_index] = 3 - nodes_colors[prev_node_index] - nodes_colors[current_node_index]
				prev_node_index = current_node_index
				current_node_index = next_node_index
				if len(nodes[next_node_index]) == 1:
					break
			cost = calculate_weight(nodes_colors, costs)
			if minimum_cost == -1 or minimum_cost > cost:
				minimum_node_colors = nodes_colors
				minimum_cost = cost
	print(minimum_cost)
	print(' '.join([str(value + 1) for value in minimum_node_colors]))

def calculate_weight(nodes, costs):
	total = 0
	for i in range(0, len(nodes)):
		total += costs[nodes[i]][i]
	return total

def get_next_node(prev_node_index, node):
	for index in node:
		if prev_node_index != index:
			return index
	return -1
main()


import sys
input = sys.stdin.readline
from collections import Counter
N = int(input())
state = [list(map(int, input().split())) for _ in range(3)]
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

def bfs(s):
	D = [-1] * N
	D[s] = 0
	q = [s]
	while q:
		qq = []
		for p in q:
			for np in graph[p]:
				if D[np] == -1:
					D[np] = D[p] + 1
					qq.append(np)
		q = qq
	return D
D = bfs(0)
ind = -1
tmp = -1
for i in range(N):
	if D[i] > tmp:
		tmp = D[i]
		ind = i
D2 = bfs(ind)
C = Counter(D2)
ok = True
for c in C.values():
	if c != 1:
		ok = False
		break
if not ok:
	print(-1)
else:
	D3 = [None] * N
	for i in range(N):
		D3[D2[i]] = i
	ind0 = D3[0]
	ind1 = D3[1]
	PPP = []
	ans = 10 ** 16
	for i1 in range(3):
		for i2 in range(3):
			if i1 == i2:
				continue
			score = state[i1][ind0] + state[i2][ind1]
			pre0 = i1
			pre1 = i2
			P = [i1, i2]
			for seq in range(2, N):
				now = 3 - pre0 - pre1
				P.append(now)
				score += state[now][D3[seq]]
				pre0 = pre1
				pre1 = now
			if score < ans:
				ans = score
				PPP = P
	toret = [None] * N
	for (i, p) in enumerate(PPP):
		toret[D3[i]] = p + 1
	print(ans)
	print(*toret)


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


def is_possible(adj, n):
	for i in range(n):
		if len(adj[i]) >= 3:
			return False
	return True

def color_pattern(adj, n):
	stack = []
	for i in range(n):
		if len(adj[i]) == 1:
			stack.append(i)
			break
	dist = [-1 for i in range(n)]
	dist[i] = 0
	while stack:
		curr = stack.pop()
		for n in adj[curr]:
			if dist[n] == -1:
				stack.append(n)
				dist[n] = (dist[curr] + 1) % 3
	return dist

def try_for_colors(n, adj, costs, pattern, seq):
	colors = []
	cost = 0
	for i in range(n):
		cost += costs[seq[pattern[i]] - 1][i]
		colors.append(seq[pattern[i]])
	return (cost, colors)
n = int(input())
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
c3 = list(map(int, input().split()))
costs = [c1, c2, c3]
adj = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	adj[u].append(v)
	adj[v].append(u)
if is_possible(adj, n):
	pattern = color_pattern(adj, n)
	(min_cost, min_colors) = try_for_colors(n, adj, costs, pattern, [1, 2, 3])
	poss = [[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
	for p in poss:
		(cost, colors) = try_for_colors(n, adj, costs, pattern, p)
		if cost < min_cost:
			min_cost = cost
			min_colors = colors
	print(min_cost)
	print(' '.join(map(str, min_colors)))
else:
	print(-1)


n = int(input())
cost = []
for _ in range(3):
	cost.append(list(map(int, input().split())))
deg = [0] * n
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
	deg[u] += 1
	deg[v] += 1
if sorted(deg) != [1, 1] + [2] * (n - 2):
	print(-1)
else:
	best = None
	best_colors = None
	root = 0
	while deg[root] != 1:
		root += 1
	for c1 in range(3):
		for c2 in range(3):
			if c1 == c2:
				continue
			c3 = 0
			while c3 in [c1, c2]:
				c3 += 1
			idx = [c1, c2, c3]
			parent = -1
			cur = root
			j = 0
			cur_cost = 0
			coloring = [-1] * n
			while True:
				i = 0
				cur_cost += cost[idx[j % 3]][cur]
				coloring[cur] = idx[j % 3] + 1
				while i < len(adj[cur]) and adj[cur][i] == parent:
					i += 1
				if i == len(adj[cur]):
					break
				parent = cur
				cur = adj[cur][i]
				j += 1
			if best is None or cur_cost < best:
				best = cur_cost
				best_colors = coloring
	print(best)
	print(*best_colors)


from collections import defaultdict
from itertools import permutations
import sys
n = int(input())
price = {}
price[0] = list(map(int, input().split()))
price[1] = list(map(int, input().split()))
price[2] = list(map(int, input().split()))
tree = defaultdict(list)
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
start = None
for node in range(1, n + 1):
	if len(tree[node]) > 2:
		print(-1)
		sys.exit(0)
	if len(tree[node]) == 1:
		start = node
best = float('inf')
best_order = None
for (c1, c2, c3) in permutations([0, 1, 2], 3):
	pointer = start
	parent = None
	current_price = 0
	for i in range(n):
		if i % 3 == 0:
			current_price += price[c1][pointer - 1]
		if i % 3 == 1:
			current_price += price[c2][pointer - 1]
		if i % 3 == 2:
			current_price += price[c3][pointer - 1]
		temp = pointer
		pointer = tree[pointer][0] if len(tree[pointer]) == 1 or tree[pointer][0] != parent else tree[pointer][1]
		parent = temp
	if current_price < best:
		best = current_price
		best_order = (c1, c2, c3)
print(best)
(c1, c2, c3) = best_order
pointer = start
parent = None
output = [0] * n
for i in range(n):
	if i % 3 == 0:
		output[pointer - 1] = str(c1 + 1)
	if i % 3 == 1:
		output[pointer - 1] = str(c2 + 1)
	if i % 3 == 2:
		output[pointer - 1] = str(c3 + 1)
	temp = pointer
	pointer = tree[pointer][0] if len(tree[pointer]) == 1 or tree[pointer][0] != parent else tree[pointer][1]
	parent = temp
print(' '.join(output))


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)
		exit()
	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 os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
n = int(input())
inf = float('INF')
c = []
for i in range(3):
	d = list(map(int, input().split()))
	c.append(d)
ll = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	ll[u - 1].append(v - 1)
	ll[v - 1].append(u - 1)
for i in range(n):
	if len(ll[i]) > 2:
		print(-1)
		exit()
	if len(ll[i]) == 1:
		a = i
pp = [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
ans = inf
mm = {i: i for i in range(n)}
w = 0
for (i, j, k) in pp:
	v = [False for _ in range(n)]
	m = 0
	cost = 0
	s = [a]
	v[a] = True
	while s:
		x = s.pop()
		mm[x] = m
		if m % 3 == 0:
			cost += c[i][x]
		elif m % 3 == 1:
			cost += c[j][x]
		else:
			cost += c[k][x]
		m += 1
		for y in ll[x]:
			if v[y]:
				continue
			s.append(y)
			v[y] = True
	if ans > cost:
		ans = cost
		ww = w
	w += 1
print(ans)
for m in range(n):
	print(pp[ww][mm[m] % 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)
		if i == n - 2:
			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()


n = int(input())
C = []
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
D = dict()
for i in range(n - 1):
	(g, h) = list(map(int, input().split()))
	if g in D:
		D[g] += [h]
	else:
		D[g] = [h]
	if h in D:
		D[h] += [g]
	else:
		D[h] = [g]
if max(list(map(len, D.values()))) >= 3:
	print(-1)
else:
	seq = []
	for i in D:
		if len(D[i]) == 1:
			seq.append(i)
			break
	A = set()
	A.add(seq[0])
	for i in range(n - 1):
		if D[seq[i]][0] in A:
			seq.append(D[seq[i]][1])
			A.add(D[seq[i]][1])
		else:
			A.add(D[seq[i]][0])
			seq.append(D[seq[i]][0])
	S = dict()
	S[123] = 0
	S[132] = 0
	S[213] = 0
	S[231] = 0
	S[321] = 0
	S[312] = 0
	for i in range(n):
		S[123] += C[i % 3][seq[i] - 1]
		S[312] += C[(i + 2) % 3][seq[i] - 1]
		S[231] += C[(i + 1) % 3][seq[i] - 1]
		S[321] += C[(2 - i) % 3][seq[i] - 1]
		S[213] += C[(1 - i) % 3][seq[i] - 1]
		S[132] += C[(0 - i) % 3][seq[i] - 1]
	MinIndex = 123
	for j in S:
		if S[j] < S[MinIndex]:
			MinIndex = j
	print(S[MinIndex])
	Ans = []
	Ans.append(MinIndex // 100)
	Ans.append(MinIndex // 10 % 10)
	Ans.append(MinIndex % 10)
	b = list()
	for i in range(n):
		b.append(0)
	for i in range(n):
		b[seq[i] - 1] = Ans[i % 3]
	for i in range(n):
		print(b[i], end=' ')


n = int(input().strip())
c1 = list(map(int, input().strip().split()))
c2 = list(map(int, input().strip().split()))
c3 = list(map(int, input().strip().split()))
c = [c1, c2, c3]
g = [[] for i in range(n)]
d = [0 for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, input().strip().split())
	g[x - 1].append(y - 1)
	g[y - 1].append(x - 1)
	d[x - 1] += 1
	d[y - 1] += 1
import sys
if max(d) >= 3:
	print(-1)
	sys.exit(0)
vis = [False for i in range(n)]
l = []
for (idx, d) in enumerate(d):
	if d == 1:
		start = idx
		break
l.append(start)
vis[start] = True
start = g[start][0]
l.append(start)
vis[start] = True
while len(g[start]) == 2:
	(x, y) = g[start]
	if vis[x] == True:
		(x, y) = (y, x)
	l.append(x)
	vis[x] = True
	start = x
t = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
cost = []
for type_ in t:
	tc = 0
	for (idx, i) in enumerate(l):
		tc += c[type_[idx % 3]][i]
	cost.append((tc, type_))
temp = min(cost)
print(temp[0])
ans = [-1 for i in range(n)]
for (idx, i) in enumerate(l):
	ans[i] = temp[1][idx % 3] + 1
print(*ans)


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)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	c = [list(map(int, input().split())) for _ in range(3)]
	path = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u1, v1) = map(int, input().split())
		path[u1 - 1].append(v1 - 1)
		path[v1 - 1].append(u1 - 1)
	st = -1
	for (ind, i) in enumerate(path):
		if len(i) > 2:
			print(-1)
			return
		if len(i) == 1:
			st = ind
	arr = [st]
	for _ in range(n - 1):
		x = path[arr[-1]]
		if len(x) == 1:
			arr.append(x[0])
		else:
			(a, b) = x
			if a == arr[-2]:
				arr.append(b)
			else:
				arr.append(a)
	dp = [[0, 1], [0, 2], [1, 2], [1, 0], [2, 0], [2, 1]]
	cost = []
	for i in range(6):
		cost.append(0)
		for j in range(2):
			cost[-1] += c[dp[i][j]][arr[j]]
	for i in range(6):
		for j in range(2, n):
			dp[i].append(3 - dp[i][-1] - dp[i][-2])
			cost[i] += c[dp[i][j]][arr[j]]
	print(min(cost))
	x = cost.index(min(cost))
	ans = []
	for (ind, i) in enumerate(dp[x]):
		ans.append((i + 1, arr[ind]))
	ans.sort(key=lambda xx: xx[1])
	for i in ans:
		print(i[0], end=' ')
	print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import Counter
(n,) = map(int, input().split())
cost = [0] * 3
for i in range(3):
	cost[i] = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
deg = Counter()
first = -1
for u in range(n):
	deg[len(g[u])] += 1
	if len(g[u]) == 1:
		first = u
if deg[2] != n - 2:
	print(-1)
else:
	second = g[first][0]
	res = 10 ** 18
	res_color = None
	for c1 in range(3):
		for c2 in range(3):
			if c1 != c2:
				color = [0] * n
				color[first] = c1
				color[second] = c2
				value = cost[c1][first] + cost[c2][second]
				(pv, v) = (first, second)
				while len(g[v]) == 2:
					next = g[v][0] if g[v][0] != pv else g[v][1]
					color[next] = 3 - (color[pv] + color[v])
					value += cost[color[next]][next]
					(pv, v) = (v, next)
				if res > value:
					res_color = color
					res = value
	assert res_color is not None
	print(res)
	print(*[c + 1 for c in res_color])


n = int(input())
color = []
for j in range(3):
	color.append(list(map(int, input().split())))
adj = [[] for i in range(n + 1)]
for j in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
ones = 0
two = 0
for j in range(1, n + 1):
	l = len(adj[j])
	if l == 1:
		ones += 1
		strt = j
	elif l == 2:
		two += 1
if ones == 2 and two == n - 2:
	j = strt
	vis = [0] * (n + 1)
	dp = [[[[[-1, -1], float('inf')] for u in range(3)] for k in range(3)] for i in range(n + 1)]
	for k in range(3):
		for q in range(3):
			if q != k:
				dp[j][k][q][1] = color[k][j - 1]
	vis = [0] * (n + 1)
	vis[j] = 1
	j = adj[strt][0]
	prev = strt
	i = 1
	while i < n:
		vis[j] = 1
		for k in range(3):
			for q in range(3):
				if k != q:
					for u in range(3):
						if u != q and u != k:
							if dp[j][k][q][1] > dp[prev][q][u][1] + color[k][j - 1]:
								dp[j][k][q][1] = dp[prev][q][u][1] + color[k][j - 1]
								dp[j][k][q][0] = [q, u]
		prev = j
		for ne in adj[prev]:
			if vis[ne] == 0:
				j = ne
		i += 1
	res = float('inf')
	col = [0] * n
	for k in range(3):
		for q in range(3):
			if res > dp[prev][k][q][1]:
				col[prev - 1] = k + 1
				ner = q
				res = dp[prev][k][q][1]
	vis = [0] * (n + 1)
	j = prev
	vis[j] = 1
	i = 1
	while i < n:
		vis[j] = 1
		prev = j
		for ne in adj[prev]:
			if vis[ne] == 0:
				j = ne
		col[j - 1] = dp[prev][col[prev - 1] - 1][ner][0][0] + 1
		ner = dp[prev][col[prev - 1] - 1][ner][0][1]
		i += 1
	print(res)
	print(*col)
else:
	print(-1)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))

def BFS(s, adj):
	parent = {s: None}
	n = len(adj)
	color = [-1] * n
	u = [s]
	ch = 0
	while u:
		nextu = []
		for i in u:
			for v in adj[i]:
				if v not in parent:
					parent[v] = i
					color[v] = ch % 3
					ch += 1
					nextu.append(v)
		u = nextu.copy()
	return color

def main():
	n = iin()
	color = [lin(), lin(), lin()]
	adj = [[] for i in range(n)]
	for _ in range(n - 1):
		(i, j) = lin()
		i -= 1
		j -= 1
		adj[i].append(j)
		adj[j].append(i)
	S = 0
	for i in range(n):
		if len(adj[i]) > 2:
			print(-1)
			return
		if len(adj[i]) == 1:
			S = i
	c1 = BFS(S, adj)
	pat = [[1, 2, 3], [2, 3, 1], [3, 2, 1], [1, 3, 2], [2, 1, 3], [3, 1, 2]]
	sol = [-1, 0]
	for p in pat:
		ch = 0
		for i in range(n):
			ch += color[p[c1[i]] - 1][i]
		if sol[0] == -1 or sol[0] > ch:
			sol = [ch, p]
	c1 = [sol[1][c1[i]] for i in range(n)]
	print(sol[0])
	print(*c1)
main()


import os
import sys
from io import BytesIO, IOBase
from itertools import permutations

def main():
	n = int(input())
	a = list(zip(map(int, input().split()), map(int, input().split()), map(int, input().split())))
	tree = [[] for _ in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		tree[x].append(y)
		tree[y].append(x)
	ele = 0
	for i in range(n):
		z = len(tree[i])
		if z > 2:
			print(-1)
			return
		if z == 1:
			ele = i
	path = []
	v = [0] * n
	while 1:
		path.append(ele)
		v[ele] = 1
		for i in tree[ele]:
			if not v[i]:
				ele = i
				break
		if len(tree[ele]) == 1:
			path.append(ele)
			break
	(mi, ans) = (10 ** 18, [])
	for i in permutations([0, 1, 2]):
		su = 0
		ans1 = [0] * n
		for j in range(n):
			su += a[path[j]][i[j % 3]]
			ans1[path[j]] = i[j % 3] + 1
		if mi > su:
			mi = su
			ans = ans1
	print(mi)
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
c = [0] * 3
c[0] = list(map(int, input().split()))
c[1] = list(map(int, input().split()))
c[2] = list(map(int, input().split()))
deg = [0] * n
g = [0] * n
for i in range(n):
	g[i] = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	deg[a - 1] += 1
	g[b - 1].append(a - 1)
	deg[b - 1] += 1
flag = 1
k = 0
for i in range(n):
	if deg[i] == 1:
		k = i
	if deg[i] > 2:
		flag = 0
if flag == 0:
	print(-1)
else:
	s = [0] * 6
	for i in range(6):
		ver = k
		vep = -1
		col = i // 2
		const = (i // 2 + i % 2) % 2 + 1
		s[i] += c[col][ver]
		for j in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + const) % 3
			s[i] += c[col][ver]
	print(min(s))
	colours = [0] * n
	ver = k
	vep = -1
	if s[0] == min(s):
		col = 0
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 1) % 3
			colours[ver] = col + 1
	elif s[1] == min(s):
		col = 0
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 2) % 3
			colours[ver] = col + 1
	elif s[2] == min(s):
		col = 1
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 2) % 3
			colours[ver] = col + 1
	elif s[3] == min(s):
		col = 1
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 1) % 3
			colours[ver] = col + 1
	elif s[4] == min(s):
		col = 2
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 1) % 3
			colours[ver] = col + 1
	else:
		col = 2
		colours[ver] = col + 1
		for i in range(n - 1):
			if g[ver][0] == vep:
				vep = ver
				ver = g[ver][1]
			else:
				vep = ver
				ver = g[ver][0]
			col = (col + 2) % 3
			colours[ver] = col + 1
	print(*colours)


import sys
from collections import defaultdict, deque

def getcost(ind, col1, col2, col3, count):
	if count == 1:
		return col1[ind - 1]
	if count == 2:
		return col2[ind - 1]
	return col3[ind - 1]
n = int(sys.stdin.readline())
col1 = list(map(int, sys.stdin.readline().split()))
col2 = list(map(int, sys.stdin.readline().split()))
col3 = list(map(int, sys.stdin.readline().split()))
tree = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, sys.stdin.readline().split())
	tree[u].append(v)
	tree[v].append(u)
z = True
leaf = []
for i in tree:
	if len(tree[i]) > 2:
		print(-1)
		z = False
		break
	if len(tree[i]) == 1:
		leaf.append(i)
if z:
	dp = defaultdict(list)
	for i in range(1, n + 1):
		dp[i] = [float('inf'), float('inf'), float('inf')]
	l = [[1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]]
	m = [0, 0, 0, 0, 0, 0]
	color = [[-1 for _ in range(n)] for x in range(6)]
	for j in range(6):
		count = 0
		cost = 0
		start = leaf[0]
		vis = defaultdict(int)
		vis[start] = 1
		q = deque()
		q.append(start)
		color[j][start - 1] = l[j][count % 3]
		cost += getcost(start, col1, col2, col3, l[j][count % 3])
		count += 1
		while q:
			a = q.popleft()
			for i in tree[a]:
				if vis[i] == 0:
					q.append(i)
					vis[i] = 1
					color[j][i - 1] = l[j][count % 3]
					cost += getcost(i, col1, col2, col3, l[j][count % 3])
					count += 1
		m[j] = cost
	ind = -1
	ans = min(m)
	print(ans)
	for i in range(6):
		if m[i] == ans:
			break
	print(*color[i])


def main():
	n = int(input())
	c0 = readIntArr()
	c1 = readIntArr()
	c2 = readIntArr()
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = readIntArr()
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	root = -1
	for i in range(n):
		if len(adj[i]) >= 3:
			print(-1)
			return
		if len(adj[i]) == 1:
			root = i
	arr = [-1] * n
	curr = root
	for i in range(n):
		arr[i] = curr
		if i + 1 < n:
			if i > 0 and adj[curr][0] == arr[i - 1]:
				curr = adj[curr][1]
			else:
				curr = adj[curr][0]
	cr = [[-1, -1, -1] for _ in range(n)]
	for i in range(n):
		cr[i][0] = c0[arr[i]]
		cr[i][1] = c1[arr[i]]
		cr[i][2] = c2[arr[i]]
	schemes = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
	minTotal = inf
	minScheme = [-1, -1, -1]
	for scheme in schemes:
		total = 0
		for i in range(n):
			total += cr[i][scheme[i % 3]]
		if total < minTotal:
			minTotal = total
			minScheme = scheme
	print(minTotal)
	ans = [-1] * n
	for i in range(n):
		ans[arr[i]] = minScheme[i % 3] + 1
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
n = int(input())
c = [list(map(int, input().split())) for i in range(3)]
g = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
for i in range(n):
	if len(g[i]) >= 3:
		print(-1)
		exit()
v = g[0][0]
ans = 10 ** 18
ans_b = []
for c0 in range(3):
	for cv in range(3):
		if c0 == cv:
			continue
		cost = 0
		b = [-1] * n
		b[0] = c0
		b[v] = cv
		cost += c[c0][0] + c[cv][v]
		q = [[v, 0, cv, c0], [0, v, c0, cv]]
		while q:
			(par, ver, cx, cy) = q.pop()
			for to in g[ver]:
				if par == to:
					continue
				if b[to] == -1:
					cz = 3 - cx - cy
					b[to] = cz
					cost += c[cz][to]
					q.append([ver, to, cy, cz])
		if cost < ans:
			ans = cost
			ans_b = b
print(ans)
for i in range(len(ans_b)):
	ans_b[i] += 1
print(*ans_b)


from collections import defaultdict
import sys
n = int(input())
ar = []
for i in range(3):
	ar.append(list(map(int, input().split())))
graph = defaultdict(list)
deg = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
	deg[a - 1] += 1
	deg[b - 1] += 1
if max(deg) > 2:
	print(-1)
	sys.exit(0)

def DFS(s, paint, cur):
	stack = []
	visited = [False] * n
	stack.append((s, cur))
	while len(stack) != 0:
		w = stack.pop()
		v = w[0]
		cur = w[1]
		visited[v] = True
		if paint[v] == 0:
			paint[v] = 6 - cur[-1] - cur[-2]
		cur.append(paint[v])
		if len(cur) == 3:
			cur = cur[1:]
		for i in graph[v]:
			if visited[i] == False:
				stack.append((i, cur + []))
	return paint
au = []
au.append([1, 2, 3])
au.append([2, 3, 1])
au.append([2, 1, 3])
au.append([3, 1, 2])
au.append([3, 2, 1])
au.append([1, 3, 2])
mi = 9999999999999999999999999
tot = []
for i in range(6):
	paint = [0] * n
	visited = [False] * n
	paint[0] = au[i][2]
	t = 0
	for j in graph[0]:
		paint[j] = au[i][t]
		t += 1
	paint = DFS(0, paint, [])
	ans = 0
	for k in range(n):
		ans += ar[paint[k] - 1][k]
	if ans < mi:
		mi = ans
		tot = paint
print(mi)
print(*tot, sep=' ')


import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	n = int(input())
	Color_info = [list(map(int, input().split())) for i in range(3)]
	ans = [-1] * n
	G = [[] for i in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		G[u].append(v)
		G[v].append(u)
	if any((len(G[i]) > 2 for i in range(n))):
		print(-1)
		return
	S = -1
	for i in range(n):
		if len(G[i]) == 1:
			S = i
			break
	Path = []
	prev_S = -1
	for i in range(n):
		Path.append(S)
		for adj in G[S]:
			if adj != prev_S:
				prev_S = S
				S = adj
				break
	COLOR = [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
	mincost = 1 << 128
	for (c1, c2, c3) in COLOR:
		c1 -= 1
		c2 -= 1
		c3 -= 1
		temp_cost = 0
		for i in range(n):
			if i % 3 == 0:
				temp_cost += Color_info[c1][Path[i]]
			elif i % 3 == 1:
				temp_cost += Color_info[c2][Path[i]]
			else:
				temp_cost += Color_info[c3][Path[i]]
		if temp_cost < mincost:
			mincost = temp_cost
			for i in range(n):
				if i % 3 == 0:
					ans[Path[i]] = c1 + 1
				elif i % 3 == 1:
					ans[Path[i]] = c2 + 1
				else:
					ans[Path[i]] = c3 + 1
	print(mincost)
	print(*ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


n = int(input())
wie = []
wie.append([-1, -1, -1])
tab = [list(map(int, input().split())) for i in range(3)]
for i in range(n):
	wie.append([tab[0][i], tab[1][i], tab[2][i]])
d = {}
for i in range(1, n + 1):
	d[i] = []
for j in range(n - 1):
	(v1, v2) = map(int, input().split())
	d[v1].append(v2)
	d[v2].append(v1)
no = 1
for i in d:
	if len(d[i]) > 2:
		print(-1)
		no = 0
		break
if no == 1:
	lista = []
	kon = 0
	for i in range(1, n + 1):
		if len(d[i]) == 1:
			kon = i
			break
	i = kon
	pop = -1
	s = 1
	rev = [0] * (n + 1)
	while s == 1:
		cur = i
		lista.append(i)
		rev[i] = len(lista) - 1
		for v in d[i]:
			if v != pop:
				i = v
				break
		pop = cur
		if len(d[i]) == 1:
			lista.append(i)
			rev[i] = len(lista) - 1
			s = 0
	dupy = []
	dupy.append([-1, -1, -1])
	for i in lista:
		dupy.append(wie[i])
	wynik = 23658267823658763485
	opti = []
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			res = 0
			res += dupy[1][i]
			res += dupy[2][j]
			c1 = i
			c2 = j
			kolory = [i, j]
			pos = 3
			while pos < n + 1:
				kol = 3 - c1 - c2
				kolory += [kol]
				res += dupy[pos][kol]
				c1 = c2
				c2 = kol
				pos += 1
			wynik = min(wynik, res)
			if wynik == res:
				opti = kolory
	print(wynik)
	kolorki = [0] * (n + 1)
	for i in range(1, n + 1):
		kolorki[i] = opti[rev[i]] + 1
	print(*kolorki[1:])