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

Input

The first line contains two integers n and m (2 ≤ n ≤ 10^5, 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

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

Examples

Note

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.