Description

You are hired to upgrade an old juice factory’s orange juice transport system. The system consists of pipes and nodes. Each pipe is bidirectional, and each pipe has a flow rate of $1$ liter per second. Pipes connect nodes, and each node can be connected to at most $3$ pipes. Nodes have infinite capacity. Nodes are labeled by integers $1$ through $n$. Before the upgrade, you need to analyze the existing system. For two distinct nodes $s$ and $t$, the $s$–$t$ flow is defined as the maximum flow from $s$ to $t$ when $s$ is the source and $t$ is the sink.

In the first sample below, the flow from $1$ to $6$ is $3$, and the flow from $1$ to $2$ is $2$.

Compute the sum of $a$–$b$ flows over all pairs of nodes with $a < b$.

Input Format

The first line contains $2$ integers $n$ and $m$ ($2\leq n\leq 3\times 10^3$, $0\leq m\leq 4500$), denoting the number of nodes and the number of pipes.

Each of the next $m$ lines contains two distinct integers $a,b$ ($1\leq a,b\leq n$), indicating that there is a pipe connecting nodes $a$ and $b$.

Each node is incident to at most $3$ pipes, and there is at most one pipe between any pair of nodes.

Output Format

Output a single integer: the sum of $a$–$b$ flows over all pairs with $a<b$.

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

36

Hint

Translated by ChatGPT 5