Juice Junctions

题目描述

一个旧果汁加工厂的运输系统由节点和双向管道组成。每条管道的容量都是每秒 $1$ 升，节点本身没有流量限制。节点编号为 $1$ 到 $n$，每个节点至多连接 $3$ 条管道。

对于两个不同的节点 $s,t$，定义 $s$ 到 $t$ 的流量为：把 $s$ 作为源点、$t$ 作为汇点时，从 $s$ 流向 $t$ 的最大流量。

请计算所有满足 $1\le a<b\le n$ 的点对 $(a,b)$ 的流量之和。

输入格式

第一行包含两个整数 $n,m$，表示节点数和管道数。

接下来 $m$ 行，每行包含两个不同的整数 $a,b$，表示一条连接节点 $a,b$ 的双向管道。

每个节点至多连接 $3$ 条管道，每对节点之间至多有一条管道。

输出格式

输出一个整数，表示所有满足 $1\le a<b\le n$ 的点对 $(a,b)$ 的最大流量之和。

样例输入 1

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

样例输出 1

36

数据范围

对于所有数据，$2\le n\le 3000$，$0\le m\le 4500$，$1\le a,b\le n$。每条管道连接两个不同节点，每对节点之间至多有一条管道，每个节点的度数不超过 $3$。输入图不保证连通。