Прочитав предлагаемые на соревнования задачи, зебра Гиппо обратила внимание на то, что в максимальном тесте к одной из задач в графе слишком мало рёбер. Тест представляет собой неориентированный граф 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 с сохранением вышеперечисленных свойств.