Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача C. Разделяй, если не властвуешь

Задачу добавил: alef

Успешно сдано решений: 5

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

После получения блокирующего пакета акций менеджеры Quantum Artificial Intelligence начали активно действовать. Для начала они наложили вето на заключение всех достаточно крупных контрактов, а также запретили заключать более двух любых контрактов в день. При этом, если заключается два контракта, это должны быть контракты с разными компаниями.

Поскольку компания Gadget Operating System и n её заказчиков хотят продолжать совместную работу, было принято решение разделить каждый из n крупных контрактов на одинаковое количество небольших контрактов.

Считайте, что компании-заказчики занумерованы числами от 1 до n.

С момента наложения вето прошло m дней, и в каждый из этих дней Gadget Operating System заключала по два контракта с теми или иными компаниями-заказчиками.

Известно, что менеджеры Gadget Operating System разделили большие контракты на небольшие оптимальным образом, так что в дальнейшем они также смогут заключать по два контракта каждый день, в том числе в последний день, в который будут заключаться контракты.

Ваша задача — определить минимальное количество k небольших контрактов, на которые были разделены крупные контракты.

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

В первой строке содержатся целые числа n и m (2 ≤ n ≤ 2000,  1 ≤ m ≤ 2000) — количество крупных контрактов и количество дней, в которые уже заключались небольшие контракты.

В каждой из следующих m строк содержится по два целых числа c(1)i и c(2)i  — номера компаний, с которыми были заключены контракты в день #i.

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

В первой строке выведите минимально возможное количество небольших контрактов k.

Пример

Входные данные
5 4
1 2
2 1
3 4
2 4
Выходные данные
4

Сдать задачу

Задать вопрос жюри по этой задаче