Sea Urchin Field

Dongeun, a native of Jeju Island, returned to Jeju after a long stay in the capital to carry on his family's trade. The son of the island's most skilled female diver, Dongeun decided to become a male diver like his parents wished. Now a new diver, he will practice diving and gather sea urchins alongside his mother. It is July to August, the sea urchin season, so there are a huge number of sea urchins in the sea.

Sea urchins can be represented as a graph made of vertices and undirected edges.

A sea urchin is a tree structure in $T=(V,E)$ where there is exactly one vertex $c \in V$ with $\deg (c)= \lvert V \rvert - 1$, and $\deg (c) \ge 3$. In a sea urchin, the vertex $c$ is called the center, and all other vertices are called the spines.

A sea urchin field is a graph that has one or more sea urchins as subgraphs. Every vertex and edge of a sea urchin field belongs to at least one sea urchin.

If a vertex is the center of a sea urchin in a field, it is not included as the center or a spine of any other sea urchin. In other words, a center belongs to exactly one sea urchin.

The spines of two different sea urchins in a field may be shared. If two sea urchins share at least one spine, they are said to be adjacent.

Each sea urchin in a field is either female or male. Since this is sea urchin season, no two adjacent sea urchins are both female or both male.

Look at the following example. The sea urchin field in the figure has sea urchins with centers 1 and 7, which are adjacent through spines 2 and 3. Every vertex and edge belongs to at least one sea urchin, and the centers 1 and 7 each belong to exactly one sea urchin.

Dongeun wants to gather these sea urchins by diving into the sea. Because he cannot stay underwater for long, he can gather exactly one sea urchin per dive. When he gathers a sea urchin, the spines of the adjacent sea urchins break and lose their value, so he cannot gather any sea urchin adjacent to the one he has gathered.

To be specific, at the start every sea urchin can be gathered. When he dives and gathers a sea urchin that can still be gathered, every sea urchin adjacent to it can no longer be gathered. Dongeun wants to gather as many sea urchins as possible, diving as many times as he needs. Find the maximum number of sea urchins he can gather.

The first line contains the number of vertices $N$ and the number of edges $M$, separated by a space. ($1 \le N \le 15\,000$, $1 \le M \le 30\,000$)

From the second line through the $M$th line, each line contains two integers $a_i$ and $b_i$, separated by a space, describing an edge. ($1 \le i \le M$, $1 \le a_i, b_i \le N$, $a_i \neq b_i$)

This means that vertex $a_i$ and vertex $b_i$ of the sea urchin field are connected by an undirected edge. No edge is given more than once.

The input is always a graph that satisfies the conditions of a sea urchin field.

Print the maximum number of sea urchins Dongeun can gather.