题目描述

给定一张$n$个点$m$条边的无向图，标号从$1$到$n$。求$\sum_{i=1}^n\sum_{j=i+1}^n \mathrm{mincut}(i,j)$。

其中$\mathrm{mincut}(x,y)$的定义为：最小的边集大小，满足删除该边集后$x,y$不连通。

输入格式

第一行输入两个数$n,m$；接下来输入$m$行，每行两个正整数表示一条边的两端点。

输出格式

输出一行，表示答案。

样例输入1

6 8
1 3
2 3
4 1
5 6
2 6
5 1
6 4
5 3

样例输出1

36

样例输入2

4 2
1 2
3 4

样例输出2

2

数据范围

对于100%的数据，$n\leq 1000000$；所有点度数$\leq 3$。保证图没有重边自环。

• Subtask 1：$n\leq 100$，20分
• Subtask 2：$n\leq 3000$，20分
• Subtask 3：$n\leq 10^6$，60分

Hint