File IO: country. in/. out

Title Description

$K$ is a country that is fond of triangles, and even people only like the triangle principle in their interactions They believe that the triangular relationship, namely $AB$ mutual recognition, $BC$ mutual recognition, and $CA$ mutual recognition, is concise and efficient In order to consolidate the triangular relationship, K country prohibits the existence of quadrilateral relationships, pentagonal relationships, and so on The so-called N-edge relationship refers to the existence of only N pairs of cognitive relationships between $N$ individuals $A_1, A_2,... A_n$: $(A_1, A_2) (A_2, A_3)... (A_n, A_1)$, without any other cognitive relationships For example, a quadrilateral relationship refers to the four individuals $AB, BC, CD,$ and $DA$ knowing each other, while $AC$ and $BD$ do not know each other During the national competition, in order to prevent cheating, it is stipulated that any pair of people who know each other cannot be on the same team. The king knows at least how many teams can be divided.

Input format

The first line consists of two integers,$N$ and $M$.

$1 \le N\le 10000, 1\le M \le 1000000$. Indicates the existence of $N$ individuals and $M$ for cognitive relationships Next $M$ line, enter a pair of friends on each line.

Output format

Output an integer indicating the minimum number of teams that can be divided

Example

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

3

Data scope and agreement

One solution $(1,3) (2) (4)$