Задача C. Психологи ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:2 сек
Входной файл:shrink.in   Ограничение памяти:64 Мб
Выходной файл:shrink.out  
Максимальный балл:100  

Условие

В самый первый день сборов по информатике специально обученные психологи с помощью программы, написанной жюри, разделили школьников на две группы таким образом, чтобы в группе были только незнакомые люди. Одной из задач психологов является поближе познакомить школьников друг с другом. Но в конце сборов пройдет еще один тренинг, поэтому будет необходимо опять разбить детей на две группы. Помогите психологам определить, какое наибольшее количество пар детей они могут познакомить, чтобы в конце сборов по-прежнему можно было бы разделить их на две группы, состоящих из незнакомых людей. Предполагайте, что школьники настолько увлечены обучением, что без помощи психологов у них нет времени знакомиться друг с другом.

Формат входного файла

В первой строке входного файла записано два натуральных числа n, m — количество детей и количество обоюдных знакомств. Далее следует m строк с описанием знакомств. В каждой строке записано два натуральных числа x и y, что показывает, что школьник x знаком с школьником y. Гарантируется, что каждое знакомство указано один раз, а так же то, что возможно разбить детей на две группы указанным выше образом.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 1000

1 ≤ m ≤ 106

1 ≤ x, y ≤ n

x ≠ y

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

№ Входной файл (shrink.in) Выходной файл (shrink.out)
1 
3 2
1 2
2 3
 
0
2 
4 2
1 2
2 3
 
2
0.041s 0.011s 15