class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        adjacency_list = []
        for i in range(N):
            adjacency_list.append(list())
        for edge in paths:
            adjacency_list[edge[0]-1].append(edge[1]-1)
            adjacency_list[edge[1]-1].append(edge[0]-1)

        #print(adjacency_list)

        colors = []
        current_color = 1
        for i in range(N):
            colors.append(-1)
        #print(colors)
        for k, vertices in enumerate(adjacency_list):
            if colors[k] == -1:
                used = []
                for vertice in vertices:
                    #print(k, vertice, colors[vertice], '==', current_color)
                    used.append(colors[vertice])
                    while current_color in used:
                        current_color += 1
                        if current_color > 4:
                            current_color = 1
            #print(k, 'final', current_color)
            colors[k] = current_color
        #print(colors)
        return colors