Сумма расстояний
Сумма расстояний
Задан связный неориентированный невзвешенный граф. Расстояние 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 - го ребра.
Между каждой парой вершин не более одного ребра.
Вихідні дані
Выведите единственное целое число - сумму расстояний между всеми неупорядоченными парами вершин в графе.
Приклад
4 4 1 2 2 3 3 1 3 4
8
7 10 1 2 2 6 5 3 5 4 5 7 3 6 1 7 5 1 7 4 4 1
34
Примітка
В первом примере расстояние между четырьмя парами вершин, соединенных ребром, равно 1, а d(1, 4) = d(2, 4) = 2.