from typing import List


def legal_graph_coloring(graph: List[List[int]], num_vertices: int, max_degree: int) -> List[int]:
    """
    Each node has at most D neighbors, and we have D+1 colors.
    So, if we look at any node, there's always at least one color that's not taken by its neighbors.
    So D+1 is always enough colors for a legal coloring.

    Time Complexity: O(num_vertices + num_edges)
    Space Complexity: O(max_degree)
    """
    all_colors = list(range(1, max_degree + 2))
    colored_vertices = [0] * num_vertices

    for vertex in range(num_vertices):
        neighboring_colors = set()

        for neighbor, connected in enumerate(graph[vertex]):
            if connected:
                neighboring_colors.add(colored_vertices[neighbor])

        for color in all_colors:
            if color not in neighboring_colors:
                colored_vertices[vertex] = color
                break
        else:
            raise AssertionError("Cannot color the graph")

    return colored_vertices