Minimum Grouping of Children

You are given n children and m pairwise contradictory relationships. Each relationship is represented by an undirected edge between two children. The contradictory relationships form an undirected graph. It is guaranteed that in the graph, there is no cycle (closed loop) containing more than 3 nodes (i.e. the only possible cycle is a triangle).

Your task is to partition the children into the minimum number of groups such that no group contains a pair of children who are contradictory. If there are no contradictions (m = 0), all children can go into one group. Otherwise, note that:

• If the graph is bipartite (i.e. it does not contain any odd cycle), 2 groups are sufficient.
• If the graph is not bipartite, then due to the special constraint (cycles can only be triangles), the only possibility is that a triangle exists and 3 groups are needed.

Determine the minimum number of groups required.

Note: All cycles in the input graph will have at most 3 nodes. In other words, if the graph is non-bipartite, it will have a 3-cycle (triangle) and the answer becomes 3.

Input Format (detailed below): First line contains two integers n and m. Then m lines follow, each containing two integers representing a contradictory pair.

inputFormat

The first line contains two integers n and m where n is the number of children (nodes) and m is the number of contradictory relationships (edges).

The following m lines each contain two integers u and v (1 ≤ u, v ≤ n), indicating that child u and child v have a contradiction.

outputFormat

Output a single integer representing the minimum number of groups needed.

• If there are no edges, output 1.
• If the graph is bipartite, output 2.
• If the graph is not bipartite (i.e. contains a triangle), output 3.

sample

5 0

1