int G[50][50]; //adjacency matrix for the graph
int num_edges; //number of edges
int num_nodes; //number of nodes

bool diff_color(int node, int color, int colored[])
{
for(int v = 0; v < node; v++)
if(G[v][node] && colored[v] == color)        //check if they have same color and
return false;                                 //if the edge exists between the two nodes.

return true;
}

bool backtracking(int colored[], int node)
{
for(int color = 0; color < 2; color++)          //try for both colors
if(diff_color(node, color, colored))
{
colored[node] = color;                    //set the color to the current vertice
if(node == num_nodes-1)               //check if the current node == last node
return true;
else
return backtracking(colored, node+1);    //backtrack it again
}
return false;
}

int main()
{
int u, v, counter;                              //input vertices that are connected
int colored[50];                                //colored vertices,
cin >> num_nodes >> num_edges;

for(int i = 0; i < 50; i++)                    //make all the vertices unconected by
for(int j = 0; j < 50; j++)                 //setting the matrix G[all][all]=0
G[i][j] = 0;

while(num_edges>0)                          //loop until all edges are entered
{
num_edges–;                                 //num_edges one less
cin >> u >> v;
G[u][v] = 1;                                 //when an edge exists then put in the
G[v][u] = 1;                                 //adjecency matrix a 1
}
if(backtracking(colored, 0))                //check if the graph is bicolorable
cout <<  “The graph can be bicolored.” << endl;
else
cout <<  “The graph can not be bicolored.” << endl;
}