Exam Hall Allocation Problem

There are \(n\) people taking a special exam. In order to maintain fairness, any two people who know each other cannot be assigned to the same exam hall. You are given the acquaintance relationships among the \(n\) people. Determine the minimum number of exam halls required so that no two acquaintances sit together.

The acquaintance relationship is provided as an undirected graph: each edge between two persons indicates that the two know each other.

Note: People are numbered from 1 to \(n\).

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of people and \(m\) is the number of pairs of acquaintances.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (\(1 \leq u,v \leq n\)), indicating that person \(u\) and person \(v\) know each other.

outputFormat

Output a single integer representing the minimum number of exam halls required so that no two acquaintances are in the same hall.

sample

3 3
1 2
2 3
1 3

3