Малі цикли
Прочитавши задачі, запропоновані для змагання, зебра Гіппо помітила, що в максимальному тесті однієї з задач у графі недостатньо ребер. Тест представлений у вигляді неорієнтованого графа G, який має такі властивості:
G — простий граф, тобто він не містить петель і кратних ребер.
G є зв'язним.
G не містить простих циклів довжиною 4 або більше. Послідовність k різних вершин v_1, ..., v_{k} називається простим циклом довжини k, якщо для кожного i вершини v_i і v_{i+1} з'єднані ребром, і, крім того, v_1 і v_k також з'єднані ребром.
Зебра Гіппо хоче додати до цього графа додаткові ребра так, щоб зберегти вищезгадані властивості. Скільки додаткових ребер вона зможе додати?
Вхідні дані
Перший рядок вхідного файлу містить два цілі числа V (1 ≤ V ≤ 10^5) і E (0 ≤ E ≤ 10^5), розділені пробілом. Тут V — кількість вершин графа G, а E — кількість ребер графа G.
Наступні E рядків описують ребра графа. i-й з цих рядків містить два цілі числа a_i і b_i (1 ≤ a_i < b_i ≤ V), розділені пробілом — номери вершин, які з'єднує i-те ребро. Вершини пронумеровані від 1 до V. Гарантується, що G має описані в умові задачі властивості.
Вихідні дані
Виведіть максимальну кількість ребер, які зебра Гіппо може додати до графа G, зберігаючи вищезгадані властивості.