human
What is a Python program to find one of the optimal paintings given the following:
I found an interesting problem on https://codeforces.com/problemset/problem/1244/D:
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 tried it in Python, but could not do it. Can you solve it?
assistant
#Here is Python program to find one of the optimal paintings.

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