16663번 - Distance Sum 다국어

문제

You are given a connected undirected unweighted graph. The distance d(u, v) between two vertices u and v is defined as the number of edges in the shortest path between them. Find the sum of d(u, v) over all unordered pairs (u, v).

입력

The first line of the input contains two integers n and m (2 ≤ n ≤ 10⁵ ; n−1 ≤ m ≤ n+ 42) — the number of vertices and the number of edges in the graph respectively. The vertices are numbered from 1 to n.

Each of the following m lines contains two integers x_i and y_i (1 ≤ x_i , y_i ≤ n; x_i ≠ y_i) — the endpoints of the i-th edge.

There is at most one edge between every pair of vertices.

출력

Output a single integer — the sum of the distances between all unordered pairs of vertices in the graph.

제한

노트

In the first example the distance between four pairs of vertices connected by an edge is equal to 1 and d(1, 4) = d(2, 4) = 2.