Minimum Graph Coloring

Given an undirected graph, find the minimum integer \( k \) such that it is possible to partition the set of vertices into \( k \) subsets where no two vertices in the same subset are adjacent (i.e. there is no edge between any two vertices in the same subset). This is equivalent to computing the chromatic number of the graph.

Note: The input graph is provided with \( n \) vertices and \( m \) edges, and the vertices are numbered from 1 to \( n \). The partitioning of the vertices must ensure that for every edge \( (u,v) \), the vertices \( u \) and \( v \) belong to different subsets.

The problem can be solved using a backtracking approach if \( n \) is small. The typical recursive strategy attempts to assign colors (or subsets) to each vertex while obeying the condition that adjacent vertices receive different colors. The goal is to minimize \( k \), the total number of colors used.

inputFormat

The first line contains two integers \( n \) and \( m \), representing the number of vertices and the number of edges in the graph, respectively. Each of the next \( m \) lines contains two integers \( u \) and \( v \) (1-indexed), indicating an undirected edge between vertices \( u \) and \( v \).

outputFormat

Output a single integer which is the minimum number \( k \) (chromatic number) needed to partition the graph into \( k \) sets such that no two vertices in any set are adjacent.

sample

3 2
1 2
2 3

2