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.

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 color vertices and 0, otherwise.

You don't need to read input or print anything. Your task is to complete the function graph coloring() which takes the 2d-array graph[], the number of colors, and the number of nodes as inputs and returns 1 if the answer exists otherwise 0.

Note: In the given 2d-array graph[], if there is an edge between vertex X and vertex Y graph[] will contain 1 at graph[X-1][Y-1], else 0.

Example:
Input :
2
4
3
5
1 2 2 3 3 4 4 1 1 3
3
2
3
1 2 2 3 1 3

Output:
1
0

//bool graphColoring(bool graph[101][101], int m, int V) {

 // vector<int> q[V];

    // for(int i=0;i<V;++i)

    // {

    //     for(int j=0;j<V;++j)

    //     {

    //         if(graph[i][j]==1)

    //         {

    //             q[i].push_back(j);

    //             q[j].push_back(i);

    //             graph[i][j]=0;

    //             graph[j][i]=0;

    //         }

    //     }

    // }

    

    // vector<int> v(V,-1);

    // v[0]=1;

    //     for(int k=1;k<V;++k)

    //     {

    //       for(int i=1;i<=m;++i) 

    //       {

    //           int f=1;

    //           for(int j=0;j<q[k].size();++j)

    //           {

    //               if(v[q[k][j]]==i)

    //               {

    //                   f=0;

    //                   break;

    //               }

    //           }

    //           if(f)

    //           {

    //           v[k]=i;

    //           break;

    //           }

    //       }

    //     //   if(v[k]==-1)

    //     //   return false;

    //     cout<<v[k]<<" ";

    // } 

    //   return true;

//}

/ { Driver Code Starts#include <bits/stdc++.h>

using namespace std;

// } Driver Code Ends

bool check(bool graph[101][101], int V, vector < int > & color, int j, int colour) {

    for (int i = 0; i < V; ++i) {

        if (graph[j][i] == 1 && color[i] == colour) return false;

    }

    return true;

}

bool graphtest(bool graph[101][101], int m, int V, vector < int > & color, int index) {

    if (V == index)

        return true;

    for (int i = 0; i < m; ++i) {

        if (check(graph, V, color, index, i)) {

            color[index] = i;

            if (graphtest(graph, m, V, color, index + 1))

                return true;

            color[index] = -1;

        }

    }

    return false;

}

bool graphColoring(bool graph[101][101], int m, int V) {

    // your code here

    vector < int > color(V, -1);

    return graphtest(graph, m, V, color, 0);

}

// { Driver Code Starts.

int main() {

    int t;

    cin >> t;

    while (t--) {

        int n, m, e;

        cin >> n >> m >> e;

        int i;

        bool graph[101][101];

        for (i = 0; i < n; i++) {

            memset(graph[i], 0, sizeof(graph[i]));

        }

        for (i = 0; i < e; i++) {

            int a, b;

            cin >> a >> b;

            graph[a - 1][b - 1] = 1;

            graph[b - 1][a - 1] = 1;

        }

        cout << graphColoring(graph, m, n) << endl;

    }

    return 0;

}

// } Driver Code Ends