P9794 [NERC 2018] Distance Sum

Translated from Problem D of [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf).

You are given a connected undirected graph with $n$ vertices and $m$ edges. Define the distance $d(u, v)$ between $u$ and $v$ as the number of edges on the shortest path from $u$ to $v$. Now, compute $\sum_{u=1}^n \sum_{v=u+1}^n d(u,v)$.

The first line contains two integers $n(1 \leq n \leq 10^5)$ and $m(n - 1 \leq m \leq n + 42)$, representing the number of vertices and the number of edges. The next $m$ lines each contain two integers $x_i$ and $y_i(1 \leq x_i,y_i \leq n, x_i \neq y_i)$, indicating that there is an edge between $x_i$ and $y_i$. It is guaranteed that there are no multiple edges or self-loops.

Output $\sum_{u=1}^n \sum_{v=u+1}^n d(u,v)$.

For all testdata, it is guaranteed that $1 \leq n \leq 10^5$, $n-1 \leq m \leq n + 42$, $1 \leq x_i, y_i \leq n$, and $x_i \neq y_i$. The graph of Sample 1 is:  In it, $d(1,2) = 1$, $d(1,3) = 1$, $d(1,4) = 2$, $d(2,3) = 1$, $d(2,3) = 2$, $d(3,4) = 1$, and the total sum is $1 + 1 + 2 + 1 + 2 + 1 = 8$. Sample 2 is:  Translated by ChatGPT 5