시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 512 MB64121018.519%

문제

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 ≤ 105 ; 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 xi and yi (1 ≤ xi , yi ≤ n; xi ≠ yi) — 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.

예제 입력 1

4 4
1 2
2 3
3 1
3 4


예제 출력 1

8


예제 입력 2

7 10
1 2
2 6
5 3
5 4
5 7
3 6
1 7
5 1
7 4
4 1


예제 출력 2

34


노트

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.