Sum of Distances in a Connected Graph

You are given a connected undirected graph with \(n\) vertices and \(m\) edges. The distance \(d(u,v)\) between two vertices \(u\) and \(v\) is defined as the number of edges on the shortest path between them.

Your task is to calculate the sum of distances for all pairs of vertices, that is, compute \[ S = \sum_{u=1}^n \sum_{v=u+1}^n d(u,v)\,. \]

inputFormat

The first line contains two integers \(n\) and \(m\) \( (2 \le n,\ n-1 \le m)\), which denote the number of vertices and edges respectively.

The following \(m\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le n\), \(u \neq v\)) representing an undirected edge between vertices \(u\) and \(v\). It is guaranteed that the graph is connected.

outputFormat

Output a single integer representing the sum of distances between every pair of vertices.

sample

3 3
1 2
2 3
1 3

3