def isSafe(k, color):
    for j in range(1, n + 1):
        if G[k][j] == 1 and x[j] == color:
            return False
    return True


def GraphColoring(k):
    for color in range(1, m + 1):
        if isSafe(k, color):
            x[k] = color

            if k == n:
                print(x[1:n + 1])
            else:
                GraphColoring(k + 1)


# Example
n = 4
m = 3

G = [
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [0, 1, 0, 1, 0]
]

x = [0] * (n + 1)

GraphColoring(1)