Problem Description

$n$ people are taking a special exam.

To ensure fairness, any two people who know each other cannot be assigned to the same exam room.

Find the minimum number of exam rooms needed to satisfy this condition.

Input Format

The first line contains an integer $n(1<n<100)$, which is the number of people taking the exam.

The second line contains an integer $m$, meaning that there are $m$ lines of data following.

Each of the next $m$ lines has the format: two integers $a$, $b$, separated by a space $(1 \le a,b \le n)$, indicating that person $a$ knows person $b$ (numbering starts from $1$).

Output Format

Output one integer on a single line, representing the minimum number of exam rooms.

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

4

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

5

Hint

Time limit: 1 second, 256M. Lanqiao Cup 2017, the 8th National Finals.

Translated by ChatGPT 5