I. Fair Diversity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

When Anatoly and Slava arrived in Bishkek, they decided to explore its most interesting cafes and restaurants as soon as possible.

To do this, the guys decided to visit two different establishments each day.

After D days, Slava realized an important problem — some establishments had been visited by the guys more often than others. In such a case, it is impossible to speak of any fair assessment!

Anatoly proposed the following plan: continue visiting two different establishments each day, but stop when all establishments have been visited the same number of times.

It is obvious that the guys want to finish their gastronomic tour sooner (to avoid spending extra money).

Help the guys find the minimum possible number of visits to each establishment in the optimal plan.

Input

The first line contains integers n and D (2 ≤ n ≤ 2000,  1 ≤ D ≤ 2000) — the number of establishments in Bishkek and the number of days during which Slava and Anatoly have already visited some of the establishments.

Each of the following D lines contains two integers fi and si (1 ≤ fi,  si ≤ n; fi ≠ si) — the numbers of the establishments that Slava and Anatoly visited on the i-th day.

Output

In a single line, output the minimum possible number of visits to each establishment in the optimal plan.

Example
Input
5 4
1 2
2 1
3 4
2 4
Output
4
Note

First test example

One possible way to optimally finish their "tour":

  • (4, 5);
  • (1, 3);
  • (5, 1);
  • (2, 5);
  • (4, 3);
  • (3, 5).

In total, each establishment will be visited 4 times:

  • Establishment 1 visited twice before the "realization" and twice after;
  • Establishment 2 visited three times before the "realization" and once after;
  • Establishment 3 visited once before the "realization" and three times after;
  • Establishment 4 visited twice before the "realization" and twice after;
  • Establishment 5 visited zero times before the "realization" and four times after.