Rings and Strings

Misawa, an artist, is trying to make a new work. Misawa prepared a large number of metal rings and black and white strings of two colors.

Misawa can make a work by repeatedly tying two different rings together with a string of either color. A ring may be tied to several rings, but each pair of rings is joined by at most one string.

Misawa wants to make a good work, since it takes effort to make one. A 'good work' is defined as follows.

• A single ring is a good work.
• Given two good works, connecting every pair of rings that are not joined by a string in either work with a white string gives one good work. (Figure 1. Operation 1)
• Swapping every white string with a black string and every black string with a white string in a good work gives a good work. (Figure 1. Operation 2)
• Only the objects defined above are good works.

Figure 1 is an example of a good work.

Figure 1. Example of a good work

Misawa finished a good work that satisfies these conditions. Misawa will select zero or more rings in this work, hang them from the ceiling, and display them. Misawa wants the black strings to stand out as much as possible. In other words, Misawa wants to maximize the number of black strings connecting a ring hanging from the ceiling with a ring that is not hanging.

Find the maximum number of black strings connecting a ring hanging from the ceiling with a ring that is not hanging, when displayed this way.

The input is given in the following format.

$N$ $M$

$u_1$ $v_1$

...

$u_M$ $v_M$

$N$ ($1 \leq N \leq 5000$) is the number of rings in the work. $M$ ($1 \leq M \leq 100000$) is the number of black strings in the work.

$u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$) mean that the $i$-th black string connects ring $u_i$ and ring $v_i$. Any pair of rings not given in the input is connected by a white string.

The work given in the input is guaranteed to be a good work.

Print the maximum number of black strings connecting a ring hanging from the ceiling with a ring that is not hanging.