Description

Explanation of the conflict constraint:

If we regard any two conflicting children as two adjacent vertices in an undirected graph, the testdata guarantees that the graph formed by the $M$ conflicting pairs contains no cycle with more than 3 vertices. (Figure 1 satisfies the requirement, while Figure 2 does not.)

Input Format

The first line contains two integers $N$ and $M$ separated by a space, indicating there are $N$ children and $M$ pairs of conflicts. Each of the next $M$ lines contains two integers $a$ and $b$ (separated by a space), meaning that child $a$ and child $b$ have a conflict. (Children are numbered starting from $1$.)

Output Format

Output one line containing a single integer — the maximum number of children the teacher can select to play the game.

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

2

Hint

There are 6 children. The conflicts contain a cycle $1 - 2 - 3$ and another cycle $3 - 4 - 5$. Therefore, you can select exactly one child from each of these two cycles, and child $3$ cannot be selected.

Constraints:

• For $20\%$ of the testdata, $1 \le N \le 20$.
• For $40\%$ of the testdata, $1 \le N \le 50$.
• For $100\%$ of the testdata, $1 \le N \le 200$.
• All $100\%$ of the testdata satisfy the conflict constraint described in the problem.

Translated by ChatGPT 5