Сума відстаней

Задано зв'язний неорієнтований неваговий граф. Відстань d(u, v) між двома вершинами u і v визначається як кількість ребер на найкоротшому шляху між ними. Знайдіть суму d(u, v) для всіх неупорядкованих пар (u, v).

Вхідні дані

Перша строка містить два цілі числа n і m (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ n + 42) - кількість вершин і кількість ребер у графі відповідно. Вершини пронумеровані від 1 до n.

Кожен з наступних m рядків містить два цілі числа x[i] і y[i] (1 ≤ x[i], y[i] ≤ n, x[i] ≠ y[i]) - кінці i-го ребра.

Між кожною парою вершин не більше одного ребра.

Вихідні дані

Виведіть єдине ціле число - суму відстаней між усіма неупорядкованими парами вершин у графі.

Приклади

Примітка

У першому прикладі відстань між чотирма парами вершин, з'єднаних ребром, дорівнює 1, а d(1, 4) = d(2, 4) = 2.