eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклад

Вхідні дані #1
4 4
1 2
2 3
3 1
3 4
Вихідні дані #1
8
Вхідні дані #2
7 10
1 2
2 6
5 3
5 4
5 7
3 6
1 7
5 1
7 4
4 1
Вихідні дані #2
34

Примітка

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

Джерело 2018 ACM NEERC, Полуфинал, Декабрь 2, Задача D