Сумма расстояний

Задан связный неориентированный невзвешенный граф. Расстояние 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.