Challenge: Color the Graph

Problem statement

Graph coloring involves finding a way of coloring the vertices of a graph.

Implement a function that finds a way of coloring a graph so that no two adjacent vertices are colored using the same color. Try using the minimum number of colors possible.

Input

The input is an undirected graph with no colors assigned.

Output

The output is a graph with all of its vertices colored in the correct way, using the minimum number of colors possible.

Sample input

Graph:

graph {0 -- 1
       0 -- 2
       1 -- 2
       1 -- 3
       2 -- 3
       3 -- 4}

Sample output

Vertex 0 , Color 0
Vertex 1 , Color 1
Vertex 2 , Color 2
Vertex 3 , Color 0
Vertex 4 , Color 1