Given an undirected graph and an integer M. The task is to determine if the graph can be colored with at most M colors such that no two adjacent vertices of the graph are colored with the same color. Here coloring of a graph means the assignment of colors to all vertices. Print 1 if it is possible to colour vertices and 0 otherwise.
Example 1:
Input:
N = 4
M = 3
E = 5
Edges[] = {(0,1),(1,2),(2,3),(3,0),(0,2)}
Output: 1
Explanation: It is possible to colour the
given graph using 3 colours.
Example 2:
Input:
N = 3
M = 2
E = 3
Edges[] = {(0,1),(1,2),(0,2)}
Output: 0
Your Task:
Your task is to complete the function graphColoring() which takes the 2d-array graph[], the number of colours and the number of nodes as inputs and returns true if answer exists otherwise false. 1 is printed if the returned value is true, 0 otherwise. The printing is done by the driver's code.
Note: In Example there are Edges not the graph.Graph will be like, if there is an edge between vertex X and vertex Y graph[] will contain 1 at graph[X-1][Y-1], else 0. In 2d-array graph[ ], nodes are 0-based indexed, i.e. from 0 to N-1.Function will be contain 2-D graph not the edges.
Expected Time Complexity: O(M^{N}).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 20
1 ≤ E ≤ (N*(N-1))/2
1 ≤ M ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3





#Function to determine if graph can be coloured with at most M colours such

#that no two adjacent vertices of graph are coloured with same colour.

def graphColoring(graph, k, V):

    

    #your code here

Solutions:
def graphColoring(graph, k, V):

	def issafe(i, graph, color, j, V):
		for k in range(V):
			if graph[i][k] == 1 and color[k] == j:
				return False
		return True

	def helper(i, graph, color, k, V):
		if i == V:
			return True
		for j in range(0, k + 0):
			if issafe(i, graph, color, j, V):
				color[i] = j
				if helper(i + 1, graph, color, k, V):
					return True
				else:
					color[i] = -1
		return False
	color = [-1] * V
	return helper(0, graph, color, k, V)


def isSafe(graph, color, col, node, n):
	for k in range(n):
		if k != node and graph[k][node] == 1 and (color[k] == col):
			return False
	return True

def solve(node, color, n, m, graph):
	if node == n:
		return True
	for i in range(1, m + 1):
		if isSafe(graph, color, i, node, n):
			color[node] = i
			if solve(node + 1, color, n, m, graph):
				return True
			color[node] = 0
	return False

def graphColoring(graph, k, V):
	color = [0] * V
	if solve(0, color, V, k, graph) == True:
		return True
	else:
		return False


def graphColoring(graph, k, V):
	color = [0] * V

	def safe(node, graph, V, color, curr):
		for j in range(V):
			if j != node and graph[j][node] == 1 and (color[j] == curr):
				return False
		return True

	def coloring(node, graph, k, V, color):
		if node == V:
			return True
		for i in range(1, k + 1):
			if safe(node, graph, V, color, i):
				color[node] = i
				if coloring(node + 1, graph, k, V, color):
					return True
				color[node] = 0
		return False
	return coloring(0, graph, k, V, color)


def is_safe(color, vertex, graph, ans, V):
	for i in range(V):
		if graph[vertex][i] == 1 and ans[i] == color:
			return False
	return True

def solve(vertex, graph, k, V, ans):
	if vertex == V:
		return True
	for color in range(k):
		if is_safe(color, vertex, graph, ans, V):
			ans[vertex] = color
			if solve(vertex + 1, graph, k, V, ans):
				return True
	return False

def graphColoring(graph, k, V):
	ans = [-1] * V
	return solve(0, graph, k, V, ans)


def graphColoring(graph, k, V):

	def validColor(node, color):
		for neighbor in range(V):
			if graph[node][neighbor] and colors[neighbor] == color:
				return False
		return True

	def backtracking(node):
		if node == V:
			return True
		for color in range(k):
			if validColor(node, color):
				colors[node] = color
				if backtracking(node + 1):
					return True
				colors[node] = -1
		return False
	colors = [-1] * V
	return backtracking(0)


from collections import defaultdict

def graphColoring(graph, k, V):
	edges = {node: [] for node in range(V)}
	for node_1 in range(len(graph)):
		for node_2 in range(node_1, len(graph[0])):
			if graph[node_1][node_2]:
				edges[node_1].append(node_2)
				edges[node_2].append(node_1)

	def dfs(node):
		if node == V:
			return True
		for color in range(1, k + 1):
			for adj_node in edges[node]:
				if color == colors[adj_node]:
					break
			else:
				colors[node] = color
				if dfs(node + 1):
					return True
				colors[node] = 0
		return False
	colors = [0] * V
	return dfs(0)


def graphColoring(graph, k, V):
	color = [0] * V
	return solve(0, graph, k, V, color)

def is_safe(node, curr_col, graph, m, n, color):
	for i in range(n):
		if i != node and graph[i][node] and (color[i] == curr_col):
			return False
	return True

def solve(node, graph, m, n, color):
	if node == n:
		return True
	for i in range(1, m + 1):
		if is_safe(node, i, graph, m, n, color):
			color[node] = i
			if solve(node + 1, graph, m, n, color):
				return True
			color[node] = 0
	return False


def graphColoring(graph, k, V):
	col = [0] * V

	def is_safe(node, i, col):
		for k in range(V):
			if k != node and col[k] == i and (graph[k][node] == 1):
				return False
		return True

	def color(node, col):
		if node == V:
			return True
		for i in range(1, k + 1):
			if is_safe(node, i, col):
				col[node] = i
				if color(node + 1, col) == True:
					return True
				col[node] = 0
		return False
	return color(0, col)


def graphColoring(graph, k, V):
	node_color = [0 for _ in range(V)]
	return graph_color(0, node_color, k, V, graph)

def graph_color(node, node_color, k, V, graph):
	if node == V:
		return True
	for color in range(1, k + 1):
		if safe_color(color, node, node_color, V, graph):
			node_color[node] = color
			if graph_color(node + 1, node_color, k, V, graph):
				return True
			node_color[node] = 0
	return False

def safe_color(color, node, node_color, V, graph):
	for v in range(V):
		if graph[node][v] == 1 and v != node and (node_color[v] == color):
			return False
	return True


def graphColoring(graph, k, V):
	adj = {i: [] for i in range(V)}
	for i in range(len(graph)):
		for j in range(len(graph[0])):
			if graph[i][j] != 0:
				adj[i].append(j)
	color = [-1] * V

	def issafe(node, c):
		for nei in adj[node]:
			if color[nei] == c:
				return False
		return True

	def solve(node):
		if node == V:
			return True
		for i in range(1, k + 1):
			if issafe(node, i):
				color[node] = i
				if solve(node + 1):
					return True
				color[node] = -1
		return False
	return solve(0)


def graphColoring(graph, k, V):
	color = [0] * (V + 1)

	def s(graph, node, c):
		for i in range(len(graph[node])):
			if graph[node][i] == 1 and color[i] == c:
				return False
		return True

	def dfs(node):
		if node == V:
			return True
		for i in range(1, k + 1):
			if s(graph, node, i):
				color[node] = i
				if dfs(node + 1):
					return True
				color[node] = 0
		return False
	return dfs(0)


def graphColoring(graph, k, V):
	d = [0] * V

	def possible(node, i):
		for j in range(V):
			if graph[node][j] == 1 and d[j] == i:
				return False
		return True

	def color(node, V):
		if node == V:
			return True
		for i in range(1, k + 1):
			if possible(node, i):
				d[node] = i
				if color(node + 1, V) == True:
					return True
				else:
					d[node] = 0
		return False
	if color(0, V) == True:
		return True
	return False


def issafe(graph, node, color, col):
	for i in range(len(graph[node])):
		if color[i] == col and graph[node][i] == 1 and (i != node):
			return 0
	return 1

def gen(graph, k, v, color, node):
	if node == v:
		return 1
	for i in range(k):
		if issafe(graph, node, color, i):
			color[node] = i
			if gen(graph, k, v, color, node + 1):
				return 1
			color[node] = -1
	return 0

def graphColoring(graph, k, V):
	color = []
	for i in range(V):
		color.append(-1)
	return gen(graph, k, V, color, 0)


def graphColoring(graph, k, V):

	def isSafeColor(curr_node, color, N, ind):
		for k in range(N):
			if k != curr_node and color[k] == ind and graph[k][curr_node]:
				return False
		return True

	def solveIt(curr_node, color, m, N, graph):
		if curr_node == N:
			return True
		for i in range(1, m + 1):
			if isSafeColor(curr_node, color, N, i):
				color[curr_node] = i
				if solveIt(curr_node + 1, color, m, N, graph):
					return True
				color[curr_node] = 0
		return False
	color = [0] * V
	if solveIt(0, color, k, V, graph):
		return True
	return False


def graphColoring(graph, m, N):
	color = [0] * N

	def p(i, ind):
		for k in range(N):
			if k != i and graph[k][i] == 1 and (color[k] == ind):
				return False
		return True

	def solve(i):
		if i == N:
			return True
		for ind in range(1, m + 1):
			if p(i, ind):
				color[i] = ind
				if solve(i + 1):
					return True
				else:
					color[i] = 0
		return False
	return solve(0)


def graphColoring(graph, k, V):
	color = [-1 for i in range(V)]

	def canColor(node, color, curColor):
		counter = -1
		for i in graph[node]:
			counter += 1
			if i != 0 and color[counter] == curColor:
				return False
		return True

	def color1(node, color):
		if node == V:
			return True
		for i in range(k):
			if canColor(node, color, i):
				color[node] = i
				if color1(node + 1, color):
					return True
				color[node] = -1
		return False
	return color1(0, color)


def isPossible(node, color, graph, colored, V):
	for adjNode in range(V):
		if graph[node][adjNode] == 1 and colored[adjNode] == color:
			return False
	return True

def rec(node, graph, colored, k, V):
	if node == V:
		return True
	for color in range(k):
		if isPossible(node, color, graph, colored, V):
			colored[node] = color
			if rec(node + 1, graph, colored, k, V):
				return True
			colored[node] = -1
	return False

def graphColoring(graph, k, V):
	colored = [-1] * V
	return rec(0, graph, colored, k, V)


def graphColoring(graph, k, V):

	def ispos(node, color, col):
		for l in range(V):
			if l != node and graph[node][l] == 1 and (color[l] == col):
				return False
		return True

	def calc(node, color):
		if node == V:
			return True
		for i in range(1, k + 1):
			if ispos(node, color, i):
				color[node] = i
				if calc(node + 1, color):
					return True
				color[node] = 0
		return False
	color = [0 for i in range(V)]
	return calc(0, color)


def color_check(col, node_i, j, graph, V):
	for k in range(V):
		if graph[node_i][k] == 1 and col[k] == j:
			return 0
	return 1

def color_node(col, node_i, graph, k, V):
	if node_i == V:
		return 1
	for j in range(k):
		if color_check(col, node_i, j, graph, V) == 1:
			col[node_i] = j
			ans = color_node(col, node_i + 1, graph, k, V)
			if ans == 1:
				return 1
			col[node_i] = -1
	return 0

def graphColoring(graph, k, V):
	col = [-1] * V
	return color_node(col, 0, graph, k, V)


def graphColoring(graph, k, N):

	def canAssign(i, j, graph, N):
		for k in range(N):
			if color[k] == j and graph[i][k] == 1:
				return False
		return True

	def solve(graph, N, i):
		if i == N:
			return True
		for j in range(k):
			if canAssign(i, j, graph, N):
				color[i] = j
				if solve(graph, N, i + 1):
					return True
				else:
					color[i] = -1
		return False
	color = [-1] * N
	return solve(graph, N, 0)


def graphColoring(graph, k, V):
	col = [0 for i in range(V + 1)]

	def isvalid(co, node):
		for i in range(V):
			if graph[node][i] == 1 and col[i] == co:
				return False
		return True

	def rec(node):
		if node == V:
			return True
		for c in range(1, k + 1):
			if isvalid(c, node):
				col[node] = c
				if rec(node + 1):
					return True
				col[node] = 0
		return False
	return rec(0)


def can_assigncolor(node, c, graph, V, color):
	for adj in range(V):
		if graph[node][adj] == 1 and color[adj] == c:
			return False
	return True

def coloring(node, graph, k, V, color):
	if node == V:
		return True
	for c in range(k):
		if can_assigncolor(node, c, graph, V, color):
			color[node] = c
			if coloring(node + 1, graph, k, V, color):
				return True
			color[node] = -1
	return False

def graphColoring(graph, k, V):
	color = [-1] * V
	return coloring(0, graph, k, V, color)


def graphColoring(graph, m, n):

	def solve(node, c, g, m, n):
		if node == n:
			return 1
		for i in range(1, m + 1):
			if isVal(node, g, c, n, i):
				c[node] = i
				if solve(node + 1, c, g, m, n):
					return 1
				c[node] = 0
		return 0

	def isVal(node, g, c, n, col):
		for k in range(n):
			if k != node and g[k][node] == 1 and (c[k] == col):
				return False
		return True
	c = [0] * n
	if solve(0, c, graph, m, n):
		return 1
	else:
		return 0


def graphColoring(graph, k, V):
	colour = [0] * V
	if solve(0, graph, k, V, colour) == True:
		return 1
	return 0

def solve(node, graph, k, V, colour):
	if node == V:
		return True
	for i in range(1, k + 1):
		if issafe(node, graph, colour, i):
			colour[node] = i
			if solve(node + 1, graph, k, V, colour):
				return True
			colour[node] = 0
	return False

def issafe(node, graph, colour, col):
	for i in range(V):
		if i != node and graph[i][node] == 1 and (colour[i] == col):
			return False
	return True


def isSafe(graph, v, colour, c, V):
	for i in range(V):
		if graph[v][i] == 1 and colour[i] == c:
			return False
	return True

def graphColourUtil(graph, m, colour, v, V):
	if v == V:
		return True
	for c in range(1, m + 1):
		if isSafe(graph, v, colour, c, V) == True:
			colour[v] = c
			if graphColourUtil(graph, m, colour, v + 1, V) == True:
				return True
			colour[v] = 0
	return False

def graphColoring(graph, k, V):
	colour = [0] * V
	if graphColourUtil(graph, k, colour, 0, V) == False:
		return False
	return True


def valid(graph, coloring, index, col, vertices):
	for edge in range(vertices):
		if graph[index][edge] == 1 and coloring[edge] == col:
			return False
	return True

def check(graph, coloring, index, colors, vertices):
	if index == vertices:
		return True
	for col in range(colors):
		if valid(graph, coloring, index, col, vertices):
			coloring[index] = col
			if check(graph, coloring, index + 1, colors, vertices):
				return True
			coloring[index] = -1
	return False

def graphColoring(graph, k, V):
	coloring = [-1] * V
	index = 0
	return check(graph, coloring, index, k, V)


from collections import defaultdict

def graphColoring(graph, k, V):
	color = [-1 for i in range(V)]
	graph1 = {i: [] for i in range(V)}
	for i in range(len(graph)):
		for j in range(len(graph[i])):
			if graph[i][j] != 0:
				graph1[i].append(j)

	def canColor(node, curColor):
		for i in graph1[node]:
			if color[i] == curColor:
				return False
		return True

	def reccur(node1):
		if node1 == V:
			return True
		for i in range(k):
			if canColor(node1, i):
				color[node1] = i
				if reccur(node1 + 1):
					return True
				color[node1] = -1
		return False
	return reccur(0)


def graphColoring(graph, k, v):
	col = [0] * v

	def isok(graph, col, c, j):
		for i in range(j):
			if graph[j][i] == 1 and col[i] == c:
				return False
		return True

	def colouring(graph, col, i, k, v):
		if i >= v:
			return True
		for c in range(1, k + 1):
			if isok(graph, col, c, i):
				col[i] = c
				if colouring(graph, col, i + 1, k, v):
					return True
				col[i] = 0
		return False
	if colouring(graph, col, 0, k, v):
		return 1
	else:
		return -1


def m_coloring_problem_helper(graph: [[]], color_arr: [], node: int, color_number: int, vertex: int):
	if node == vertex:
		return True
	for i in range(1, color_number + 1):
		if is_safe(graph, color_arr, node, i):
			color_arr[node] = i
			if m_coloring_problem_helper(graph, color_arr, node + 1, color_number, vertex):
				return True
			color_arr[node] = 0
	return False

def is_safe(graph: [[]], color_arr: [], node, color):
	adjacent_neighbours = graph[node]
	for i in range(0, len(adjacent_neighbours)):
		if adjacent_neighbours[i] != 0 and color_arr[i] == color:
			return False
	return True

def graph_color(graph: [[]], k, v):
	color_arr = [0] * v
	return m_coloring_problem_helper(graph, color_arr, 0, k, v)

def graphColoring(graph, k, V):
	return graph_color(graph, k, V)


def graphColoring(graph, k, V):
	g = Graph(V)
	g.graph = graph
	return g.graphColouring(k)

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

	def isSafe(self, v, colour, c):
		for i in range(self.V):
			if self.graph[v][i] == 1 and colour[i] == c:
				return False
		return True

	def graphColourUtil(self, m, colour, v):
		if v == self.V:
			return True
		for c in range(1, m + 1):
			if self.isSafe(v, colour, c) == True:
				colour[v] = c
				if self.graphColourUtil(m, colour, v + 1) == True:
					return True
				colour[v] = 0

	def graphColouring(self, m):
		colour = [0] * self.V
		if self.graphColourUtil(m, colour, 0) == None:
			return 0
		return 1


def issafe(i, j, graph, color, n):
	for x in range(n):
		if (graph[i][x] == 1 or graph[x][i] == 1) and color[x] == j:
			return False
	return True

def solve(i, color, graph, m, n):
	if i == n:
		return True
	for j in range(1, m + 1):
		if issafe(i, j, graph, color, n):
			color[i] = j
			if solve(i + 1, color, graph, m, n):
				return True
			color[i] = 0
	return False

def graphColoring(graph, m, n):
	color = [0] * n
	if solve(0, color, graph, m, n):
		return True
	return False


def graphColoring(graph, k, V):

	def canAssign(i, j, graph, V):
		for k in range(V):
			if graph[i][k] == 1 and color[k] == j:
				return False
		return True

	def helper(graph, V, i):
		if i == V:
			return True
		for j in range(k):
			if canAssign(i, j, graph, V):
				color[i] = j
				if helper(graph, V, i + 1):
					return True
				color[i] = -1
		return False
	color = [-1] * V


def graphColoring(graph, k, V):
	from collections import defaultdict
	col = [-1 for i in range(V)]

	def ispossible(color, src):
		for i in range(V):
			if graph[src][i] == 1 and col[i] == color:
				return False
		return True

	def recursion(src, col):
		if src >= V:
			return True
		for i in range(k):
			if ispossible(i, src):
				col[src] = i
				if recursion(src + 1, col):
					return True
				col[src] = -1
		return False
	return recursion(0, col)


def graphColoring(graph, k, V):
	col = [0 for i in range(V)]

	def ispossible(graph, idx, c):
		for i in range(V):
			if graph[idx][i] == 1 and col[i] == c:
				return False
		return True

	def rec(idx):
		if idx == V:
			return True
		for c in range(1, k + 1):
			if ispossible(graph, idx, c):
				col[idx] = c
				if rec(idx + 1):
					return True
				else:
					col[idx] = 0
		return False
	return rec(0)


def is_color_safe(ar, n, curr_ver, color_to_check, color_dict):
	for each_v in range(n):
		if ar[curr_ver][each_v] == 1:
			if color_dict[each_v] == color_to_check:
				return False
	return True

def check_color_possible(ar, m, n, color_dict, curr_ver=0):
	if curr_ver == n:
		for (each_v, each_c) in color_dict.items():
			if each_c == -1:
				return False
		return True
	if color_dict[curr_ver] != -1:
		return check_color_possible(ar, m, n, color_dict, curr_ver + 1)
	for each_color in range(m):
		if is_color_safe(ar, n, curr_ver, each_color, color_dict):
			color_dict[curr_ver] = each_color
			if check_color_possible(ar, m, n, color_dict, curr_ver + 1):
				return True
			color_dict[curr_ver] = -1
	return False

def graphColoring(graph, k, V):
	color_dict = {each_v: -1 for each_v in range(V)}
	return check_color_possible(graph, k, V, color_dict)


def graphColoring(graph, m, V):

	def isSafe(graph, color, vertex, c):
		for i in range(len(graph)):
			if graph[vertex][i] == 1 and color[i] == c:
				return False
		return True

	def graphColoringUtil(graph, m, color, vertex):
		if vertex == len(graph):
			return True
		for c in range(1, m + 1):
			if isSafe(graph, color, vertex, c):
				color[vertex] = c
				if graphColoringUtil(graph, m, color, vertex + 1):
					return True
				color[vertex] = 0
		return False
	color = [0] * len(graph)
	if graphColoringUtil(graph, m, color, 0):
		return 1
	else:
		return 0


def isValid(graph, v, col, color, V):
	for k in range(V):
		if graph[v][k] == 1 and color[k] == col:
			return False
	return True

def isPossible(graph, k, node, color, V):
	if node == V:
		return True
	for j in range(1, k + 1):
		if isValid(graph, node, j, color, V):
			color[node] = j
			if isPossible(graph, k, node + 1, color, V):
				return True
			color[node] = 0
	return False

def graphColoring(graph, k, V):
	color = [0 for _ in range(V)]
	return isPossible(graph, k, 0, color, V)


def graphColoring(graph, m, n):
	color = [-1] * n
	if Util(0, graph, m, n, color):
		return True
	return False

def Util(node, graph, m, n, color):
	if node == n:
		return True
	for cl in range(1, m + 1):
		if canColor(cl, node, graph, color):
			color[node] = cl
			if Util(node + 1, graph, m, n, color):
				return True
			color[node] = -1
	return False

def canColor(cl, node, graph, color):
	for (index, nei) in enumerate(graph[node]):
		if nei == 1 and color[index] == cl:
			return False
	return True


def graphColoring(graph, k, V):
	color = [-1] * V

	def canColor(node, col):
		for k in range(V):
			if k != node and graph[k][node] == 1 and (color[k] == col):
				return False
		return True

	def rec(node):
		if node == V:
			return True
		for col in range(k):
			if canColor(node, col):
				color[node] = col
				if rec(node + 1) == True:
					return True
				color[node] = -1
		return False
	return rec(0)


def graphColoring(graph, k, V):

	def isSafe(col, node, color):
		for u in range(V):
			if u != node and graph[u][node] == 1 and (color[u] == col):
				return False
		return True

	def backtrack(node, color):
		if node == V:
			return True
		for i in range(1, k + 1):
			if isSafe(i, node, color):
				color[node] = i
				if backtrack(node + 1, color):
					return True
				color[node] = 0
		return False
	color = [0] * V
	if backtrack(0, color):
		return True
	return False


def graphColoring(graph, k, V):
	color = [0] * V

	def isSafe(node, i):
		for k in range(V):
			if graph[node][k] == 1 and color[k] == i:
				return False
		return True

	def helper(node):
		if node == V:
			return True
		for i in range(1, k + 1):
			if isSafe(node, i):
				color[node] = i
				if helper(node + 1):
					return True
				color[node] = 0
		return False
	return helper(0)


def graphColoring(graph, k, V):
	n = len(graph)
	d = [0] * V

	def solve(node, V):
		if node == V:
			return True
		for i in range(1, k + 1):
			if issafe(node, i):
				d[node] = i
				if solve(node + 1, V) == True:
					return True
				else:
					d[node] = 0
		return False

	def issafe(node, i):
		for j in range(V):
			if graph[node][j] == 1 and d[j] == i:
				return False
		return True
	if solve(0, V) == True:
		return True
	return False


def createMost(graph):
	k = {}
	for i in range(len(graph)):
		l = []
		for j in range(len(graph[i])):
			if graph[i][j] == 1:
				l.append(j)
		k[i] = l
	return k

def checkMost(takem, f, color, i1):
	for (i, j) in takem.items():
		if i == f:
			for m in j:
				if color[m] == i1:
					return True
			return False
	return False

def graphColoring(graph, k, V):
	color = [-1] * V
	takem = createMost(graph)
	node = 0

	def helper(takem, node, k, V, color):
		if node == V:
			return True
		for i in range(k):
			if checkMost(takem, node, color, i) == False:
				color[node] = i
				if helper(takem, node + 1, k, V, color) == True:
					return True
			color[node] = -1
		return False
	return helper(takem, node, k, V, color)


def isValid(color, c, node, graph, v, k):
	for i in range(v):
		if graph[node][i] == 1 and c[i] == color:
			return False
	return True

def helper(node, c, graph, k, v):
	if node == v:
		return True
	for i in range(1, k + 1):
		if isValid(i, c, node, graph, v, k) == True:
			c[node] = i
			if helper(node + 1, c, graph, k, v) == True:
				return True
			c[node] = 0
	return False

def graphColoring(graph, k, V):
	c = [0] * V
	return helper(0, c, graph, k, V)


def isSafe(node, color, graph, N, i):
	for j in range(N):
		if j != node and graph[node][j] == 1 and (color[j] == i):
			return False
	return True

def canColor(node, color, k, V, graph):
	if node == V:
		return True
	for i in range(1, k + 1):
		if isSafe(node, color, graph, V, i):
			color[node] = i
			if canColor(node + 1, color, k, V, graph):
				return True
			color[node] = 0
	return False

def graphColoring(graph, k, V):
	color = [0] * V
	if canColor(0, color, k, V, graph):
		return True
	return False


def isSafe(graph, m, v, nodeColor, index, color):
	for node in range(v):
		if graph[index][node] == 1 and nodeColor[node] == color:
			return False
	return True

def solve(graph, m, v, nodeColor, index):
	if index == v:
		return True
	for color in range(1, m + 1):
		if isSafe(graph, m, v, nodeColor, index, color):
			nodeColor[index] = color
			if solve(graph, m, v, nodeColor, index + 1):
				return True
	return False

def graphColoring(graph, m, v):
	nodeColor = [0] * v
	return solve(graph, m, v, nodeColor, 0)


def isSafe(graph, m, v, nodeColor, index, color):
	for col in range(v):
		if graph[index][col] == 1 and nodeColor[col] == color:
			return False
	return True

def helper(graph, m, v, nodeColor, index):
	if index == v:
		return True
	for color in range(1, m + 1):
		if isSafe(graph, m, v, nodeColor, index, color):
			nodeColor[index] = color
			if helper(graph, m, v, nodeColor, index + 1):
				return True
			else:
				nodeColor[index] = 0
	return False

def graphColoring(graph, m, v):
	nodeColor = [0] * v
	return helper(graph, m, v, nodeColor, 0)


def is_safe(vertex, color, graph, arr, V):
	for i in range(V):
		if graph[vertex][i] == 1 and arr[i] == color:
			return False
	return True

def solve(vertex, graph, arr, M, V, ans):
	if vertex == V:
		return True
	for c in range(M):
		if is_safe(vertex, c, graph, arr, V):
			arr[vertex] = c
			is_next_possible = solve(vertex + 1, graph, arr, M, V, ans)
			if is_next_possible:
				return True
			arr[vertex] = -1

def graphColoring(graph, M, V):
	ans = []
	arr = [-1] * V
	solve(0, graph, arr, M, V, ans)
	return solve(0, graph, arr, M, V, ans)


def isSafe(node, col, color, graph, v):
	for i in range(v):
		if i != node and graph[node][i] == 1 and (color[i] == col):
			return False
	return True

def solve(node, graph, k, v, color):
	if node == v:
		return True
	for i in range(1, k + 1):
		if isSafe(node, i, color, graph, v):
			color[node] = i
			if solve(node + 1, graph, k, v, color):
				return True
			color[node] = 0
	return False

def graphColoring(graph, k, V):
	color = [0] * V
	if solve(0, graph, k, V, color):
		return True
	return False


import collections

def graphColoring(graph, k, V):
	return check(0, k, [0] * V, graph, V)

def check(node, m, colors, graph, n):
	if node == n:
		return True
	for color in range(1, m + 1):
		if canColor(node, color, graph, colors):
			colors[node] = color
			if check(node + 1, m, colors, graph, n):
				return True
			colors[node] = 0

def canColor(node, color, graph, colors):
	for i in range(len(graph)):
		if i != node and colors[i] == color and graph[node][i]:
			return False
	return True


def graphColoring(g, m, n):

	def isSafe(i, c):
		for j in range(n):
			if g[i][j] and col[j] == c:
				return False
		return True
	col = [-1] * n

	def dfs(i):
		if i == n:
			return True
		for c in range(m):
			if isSafe(i, c):
				temp = col[i]
				col[i] = c
				if dfs(i + 1):
					return True
				col[i] = temp
		return False
	return dfs(0)


def check(graph, k, V, colors, node, color):
	for i in range(V):
		if graph[node][i] == 1 and colors[i] == color:
			return False
	return True

def util(graph, k, V, colors, i):
	if i == V:
		return True
	for c in range(k):
		if check(graph, k, V, colors, i, c):
			colors[i] = c
			if util(graph, k, V, colors, i + 1):
				return True
	return False

def graphColoring(graph, k, V):
	colors = [-1 for i in range(V)]
	return util(graph, k, V, colors, 0)


def graphColoring(graph, k, V):
	colors = [-1 for i in range(V)]
	return color(graph, k, V, colors, 0)

def color(graph, k, V, colors, i):
	if i == V:
		return True
	for c in range(k):
		if isSafe(graph, V, i, c, colors):
			colors[i] = c
			if color(graph, k, V, colors, i + 1):
				return True
	return False

def isSafe(graph, V, i, c, colors):
	for v in range(V):
		if graph[i][v] == 1 and colors[v] == c:
			return False
	return True


def issafe(graph, c, i, V, col):
	for v in range(V):
		if graph[i][v] == 1 and col[v] == c:
			return False
	return True

def fun(graph, k, V, i, col):
	if i == V:
		return True
	for c in range(k):
		if issafe(graph, c, i, V, col):
			col[i] = c
			if fun(graph, k, V, i + 1, col):
				return True
			col[i] = -1
	return False

def graphColoring(graph, k, V):
	col = [-1] * V
	return fun(graph, k, V, 0, col)


def iscolour(node, colour, graph, n, col):
	for i in range(n):
		if i != node and graph[i][node] == 1 and (colour[i] == col):
			return False
	return True

def solution(node, colour, m, n, graph):
	if node == n:
		return True
	for i in range(1, m + 1):
		if iscolour(node, colour, graph, n, i):
			colour[node] = i
			if solution(node + 1, colour, m, n, graph):
				return True
			else:
				colour[node] = 0
	return False

def graphColoring(graph, m, n):
	colour = [0] * n
	return True if solution(0, colour, m, n, graph) else False


def graphColoring(graph, k, V):
	colour_map = {}
	for i in range(0, V):
		colour_map[i] = -1
	ans = dfs(0, graph, k, V, colour_map)
	if ans is True:
		return True
	else:
		return False

def dfs(v, graph, k, V, colour_map):
	if v == V:
		return True
	for c in range(0, k):
		check = check_colour(v, graph, k, V, colour_map, c)
		if check is True:
			colour_map[v] = c
			ans = dfs(v + 1, graph, k, V, colour_map)
			if ans is True:
				return True
			colour_map[v] = -1
	return False

def check_colour(v, graph, k, V, colour_map, c):
	for i in range(0, V):
		if i == v:
			continue
		elif graph[i][v] == 1:
			if colour_map[i] == c:
				return False
	return True


def is_valid(A, x, c, graph):
	for i in range(len(graph[x])):
		if graph[x][i] == 1:
			if A[i] == c:
				return False
	return True

def helper(A, x, k, graph):
	if x == len(A):
		return True
	for i in range(k):
		if is_valid(A, x, i, graph):
			A[x] = i
			if helper(A, x + 1, k, graph):
				return True
			else:
				A[x] = None
	return False

def graphColoring(graph, k, V):
	A = [None for x in range(V)]
	return helper(A, 0, k, graph)


def can_color(node, graph, c, col, V):
	for v in range(V):
		if v != node and col[v] == c and (graph[node][v] == 1):
			return False
	return True

def color_graph(node, graph, col, k, V):
	if node == V:
		return True
	for c in range(1, k + 1):
		if can_color(node, graph, c, col, V):
			col[node] = c
			if color_graph(node + 1, graph, col, k, V):
				return True
			col[node] = -1
	return False

def graphColoring(graph, k, V):
	col = {}
	for i in range(V):
		col[i] = -1
	if color_graph(0, graph, col, k, V):
		return 1
	return 0


def graph_matrix_to_list(graph, V):
	adj = {}
	for i in range(V):
		adj[i] = []
	for i in range(V):
		for j in range(V):
			if graph[i][j] == 1:
				adj[i].append(j)
	return adj

def graphColoring(graph, k, V):
	adj = graph_matrix_to_list(graph, V)

	def initialize():
		coloring = {}
		possible = [set(range(k)) for v in range(V)]
		color_count = {}
		for c in range(k):
			color_count[c] = 0
		coloring[0] = 0
		possible[0] = None
		color_count[0] += 1
		for i in adj[0]:
			possible[i].remove(0)
		return {'coloring': coloring, 'possible': possible, 'color_count': color_count, 'count': 1}

	def isSolution(p):
		return p['count'] == V

	def actions(p):
		if isSolution(p):
			return []
		ac = []
		possible = p['possible']
		i = None
		for j in range(V):
			if possible[j] != None:
				if i == None or len(possible[j]) < len(possible[i]):
					i = j
		unused_color = False
		for c in possible[i]:
			if p['color_count'][c] > 0 or not unused_color:
				if p['color_count'][c] == 0:
					unused_color = True
				neighbours = []
				for j in adj[i]:
					if possible[j] != None and c in possible[j]:
						neighbours.append(j)
				ac.append({'i': i, 'c': c, 'possible': possible[i], 'neighbours': neighbours})
		return ac

	def take_action(p, ac):
		p['count'] += 1
		possible = p['possible']
		i = ac['i']
		c = ac['c']
		p['coloring'][i] = c
		p['color_count'][c] += 1
		possible[i] = None
		for j in ac['neighbours']:
			possible[j].remove(c)

	def undo_action(p, ac):
		p['count'] -= 1
		possible = p['possible']
		i = ac['i']
		c = ac['c']
		del p['coloring'][i]
		p['color_count'][c] -= 1
		possible[i] = ac['possible']
		for j in ac['neighbours']:
			possible[j].add(c)

	def process(p):
		return 1
	partial = initialize()

	def inner():
		if isSolution(partial):
			return process(partial)
		else:
			for ac in actions(partial):
				take_action(partial, ac)
				out = inner()
				if out is not None:
					return out
				undo_action(partial, ac)
	out = inner()
	if out == None:
		return 0
	else:
		return out


from collections import defaultdict

def graphColoring(graph, k, N):
	color = [0] * N

	def isSafe(node, c):
		for x in range(N):
			if x != node and graph[x][node] == 1 and (color[x] == c):
				return False
		return True

	def solve(node):
		if node == N:
			return True
		for i in range(1, k + 1):
			if isSafe(node, i):
				color[node] = i
				if solve(node + 1):
					return True
				color[node] = 0
		return False
	return solve(0)


def graphColoring(graph, k, V):
	color = [0] * V

	def issafe(node, curr):
		for i in range(V):
			if graph[node][i] == 1 and color[i] == curr:
				return False
		return True

	def fillColor(node):
		if node == V:
			return True
		for rang in range(1, k + 1):
			if issafe(node, rang):
				color[node] = rang
				if fillColor(node + 1):
					return True
				color[node] = 0
		return False
	return fillColor(0)


def isSafe(node, graph, color, n, col):
	for i in range(n):
		if i != node and graph[i][node] == 1 and (color[i] == col):
			return False
	return True

def mColoring(node, graph, color, n, m):
	if node == n:
		return True
	for i in range(1, m + 1):
		if isSafe(node, graph, color, n, i):
			color[node] = i
			if mColoring(node + 1, graph, color, n, m):
				return True
			color[node] = 0
	return False

def graphColoring(graph, m, n):
	color = [0] * n
	return mColoring(0, graph, color, n, m)