Distance Sum — Eolymp

Input

The first line contains two integers $n$ and $m$ ( $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5, $n - 1 \leq m \leq n + 42$ n - 1 \le m \le 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}$ x_i and $y_{i}$ y_i ( $1 \leq x_{i}, y_{i} \leq n$ 1 \le x_i, y_i \le n, $x_{i} \neq = y_{i}$ x_i \ne 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

Example 1

Loading

Example 2

Loading

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$ d(1, 4) = d(2, 4) = 2.