Задан связный неориентированный невзвешенный граф. Расстояние d (u, v) между двумя вершинами u и v определяется как количество ребер на кратчайшем пути между ними. Найдите сумму d (u, v) по всем неупорядоченным парам (u, v).

Входные данные

Первая строка содержит два целых числа n и m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ n + 42) - количество вершин и количество ребер в графе соответственно. Вершины пронумерованы от 1 до n.

Каждая из следующих m строк содержит два целых числа xi и yi (1 ≤ xi, yi ≤ n, xi ≠ yi) - концы i - го ребра.

Между каждой парой вершин не более одного ребра.

Выходные данные

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

Пояснение

В первом примере расстояние между четырьмя парами вершин, соединенных ребром, равно 1, а d(1, 4) = d(2, 4) = 2.