I. Справедливое разнообразие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда Анатолий и Слава приехали в Бишкек, они решили как можно скорее изучить его самые интересные кафе и рестораны.

Для этого ребята решили каждый день посещать два различных заведения.

Спустя D дней Слава осознал важную проблему — какие-то заведения были посещены ребятами чаще, чем другие. В таком случае нельзя говорить ни о какой справедливой оценке!

Анатолий предложил следующий план: продолжить каждый день посещать по два различных заведения, но остановиться, когда все заведения будут посещены одинаковое количество раз.

Очевидно, что ребятам хочется закончить гастрономический тур пораньше (чтобы не тратить лишние деньги).

Помогите ребятам найти минимально возможное количество посещений каждого заведения в оптимальном плане.

Входные данные

В первой строке содержатся целые числа n и D (2 ≤ n ≤ 2000,  1 ≤ D ≤ 2000) — количество заведений в Бишкеке и количество дней, в которые Слава и Анатолий уже посетили какие-то из заведений.

В каждой из следующих D строк содержится по два целых числа fi и si (1 ≤ fi,  si ≤ n; fi ≠ si) — номера заведений, которые посетили Слава и Анатолий в i-й день.

Выходные данные

В единственной строке выведите минимально возможное количество посещений каждого заведения в оптимальном плане.

Пример
Входные данные
5 4
1 2
2 1
3 4
2 4
Выходные данные
4
Примечание

Первый тестовый пример

Один из возможных способов оптимально закончить свой «поход»:

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

Суммарно каждое заведение будет посещено по 4 раза:

  • Заведение 1 посещено два раза до «осознания» и два — после;
  • Заведение 2 посещено три раза до «осознания» и один — после;
  • Заведение 3 посещено один раз до «осознания» и три — после;
  • Заведение 4 посещено два раза до «осознания» и два — после;
  • Заведение 5 посещено ноль раз до «осознания» и четыре — после.