Minimum Clique Cover in Graphs

Given an undirected graph (G = (V, E)) with (N) nodes and (M) edges, determine the minimum number of cliques required to cover all vertices. A clique is a subset of vertices where every two distinct vertices are connected by an edge. Note that a single vertex is considered a clique. Each vertex must belong to exactly one clique.

Formally, given the graph (G), partition the vertex set (V) into (k) subsets (V_1, V_2, \dots, V_k) such that for each (i), the induced subgraph on (V_i) is a complete graph. Your task is to find the minimum possible (k).

inputFormat

The input is read from standard input (stdin). The first line contains two integers (N) and (M), denoting the number of nodes and the number of edges in the graph respectively. The following (M) lines each contain two integers (u) and (v), indicating an undirected edge between nodes (u) and (v). Nodes are numbered from 1 to (N).

outputFormat

Output a single integer to standard output (stdout), representing the minimum number of cliques required to cover all nodes.## sample

4 6
1 2
1 3
1 4
2 3
2 4
3 4

1