P3196 [HNOI2008] A Magical Country

Country K is obsessed with triangles; even interpersonal relationships follow a triangle principle. They consider a triangle relationship—namely, $A B$, $B C$, and $C A$ are mutually acquainted—to be simple and efficient. To reinforce triangle relationships, Country K forbids the existence of four-cycle relationships, five-cycle relationships, and so on. An $N$-cycle relationship means that among $N$ people $A_1, A_2, \ldots, A_n$, there exist exactly $N$ acquaintance pairs: $(A_1, A_2)$, $(A_2, A_3)$, $\ldots$, $(A_n, A_1)$, and no other acquaintance pairs among them. For example, a four-cycle relationship means that among $A, B, C, D$, the pairs $(A, B)$, $(B, C)$, $(C, D)$, $(D, A)$ are mutually acquainted, while $(A, C)$ and $(B, D)$ are not acquainted. During a national contest, to prevent cheating, it is required that any two people who are acquainted must not be placed on the same team. The king wants to know the minimum number of teams needed.

The first line contains two integers $N$ and $M$ ($1 \le N \le 10000$, $1 \le M \le 1000000$), indicating there are $N$ people and $M$ acquaintance pairs. The next $M$ lines each contain one pair of friends.

Output a single integer: the minimum number of teams.

One possible arrangement: (1, 3) (2) (4). Translated by ChatGPT 5