Задача C. Разделяй, если не властвуешь
Задачу добавил: alef
Успешно сдано решений: 6
После получения блокирующего пакета акций менеджеры 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