M - Coloring Problem Statement

Given an undirected graph with 'N' nodes in the form of an adjacency matrix and an integer 'M', determine if it is possible to color the vertices of the graph using at most 'M' colors such that no two adjacent vertices share the same color.

Input:

The first line contains a single integer T, representing the number of test cases. Each test case consists of:
 - Two space-separated integers N and M in the first line.
 - The following N lines contain N integers each, representing a row of the adjacency matrix.

Output:

Print “Yes” for each test case if the graph can be colored with at most M colors, otherwise print “No”.

Example:

Input:

2
3 3
0 1 0
1 0 1
0 1 0
3 2
0 1 1
1 0 1
1 1 0

Output:

Yes
No

Explanation:

For the first test case, coloring vertices 1, 2, and 3 with different colors is possible using at most 3 colors which satisfies the condition. For the second test case, it is impossible to color the graph with only 2 colors without two adjacent vertices sharing the same color.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 20
• 1 ≤ M ≤ N

Note: You do not need to print the outputs yourself, just implement the function that will generate the answer.