Problem Description

In the CEOI community garden, we are growing a collection of special flowers that tightly knit their roots together. If we cut them, they regrow, as long as we do not cut too aggressively and cause irreparable damage.

If a pair of flowers, $a$ and $b$, knit their roots together, we call them "connected". Otherwise, they are "disconnected". Roots grow according to the following rule: Let $a$ and $b$ be two disconnected flowers. If at least $2$ other flowers $c$ and $d$ exist, such that each of $a$ and $b$ is connected with both $c$ and $d$, then roots between $a$ and $b$ will grow, and they will become connected.

These flowers have now been growing for a while, and all the roots that could grow by following the above rule have grown. In other words, if two flowers $a$ and $b$ are both connected with some flowers $c$ and $d$, then $a$ and $b$ are guaranteed to be connected with each other.

We need to uproot this garden and move it to the next CEOI location. To simplify the migration, we would like to cut as many roots as possible. However, we want the flowers to regrow back into their current state. What is the maximum number of connected pairs of flowers that we may cut so that they still regrow back into their current state? It does not matter how many iterations of growth it would take.

Input Format

The first line of the input contains two space-separated integers $n$ and $m$, the number of flowers and the number of existing connections between them. This is followed by $m$ lines, each containing a pair of integers $a_i$ and $b_i$, indicating that flowers $a_i$ and $b_i$ are connected. Flowers are marked with integers $1\ldots n$. The input is guaranteed to follow the rule described in the task description.

Output Format

Output a single integer - the maximum number of connections that we may cut.

9 14
1 2
1 4
1 5
2 4
2 5
3 4
4 5
3 6
4 6
6 7
6 9
7 9
8 9
5 8

2

Hint

Comment

The flowers in the example before any cutting. One can check that no additional connections can form based on the described growth procedure.

:::align{center} :::

The flowers in the example after the cutting have $2$ connections less. The connection between $1$ and $2$ can regrow because flowers $1$ and $2$ are both connected to flowers $4$ and $5$. Similarly, the connection between $4$ and $5$ can regrow because flowers $4$ and $5$ are both connected to flowers $1$ and $2$.

:::align{center} :::

Constraints

• $1\le n\le 1000$
• $1\le m\le 10^5$

Subtasks

• Subtask $1$ ($20$ points): $n\le 10$ and $m\le 20$
• Subtask $2$ ($14$ points): $m=\dfrac{n(n-1)}{2}$
• Subtask $3$ ($15$ points): We guarantee that each flower is connected with at most $7$ other flowers.
• Subtask $4$ ($15$ points): $n\le 50$ and $m\le 1000$
• Subtask $5$ ($36$ points): No additional constraints.