M-Coloring Problem Statement

Given an undirected graph as an adjacency matrix and an integer M, determine whether you can color the vertices of the graph using at most M colors such that no two adjacent vertices share the same color.

Example:

Input:

adjacencyMatrix = [
[0, 1, 0],
[1, 0, 1],
[0, 1, 0]
], M = 3

Output:

"YES"

Explanation:

The adjacency matrix indicates that vertex 1 is connected to vertex 2, and vertex 2 is connected to vertex 3. It is possible to color the graph using 2 colors (e.g., coloring vertex 1 with color 2, vertex 2 with color 1, and vertex 3 with color 2), which is ≤ M.

Constraints:

• 1 ≤ T ≤ 1000
• 1 ≤ V ≤ 20
• 1 ≤ M ≤ V
• Time Limit: 1 sec