Background

Translated from Problem D of NERC 2018.

Problem Description

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)$.

Input Format

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 Format

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

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

Hint

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