Juice Junctions

Time limit7sMemory limit512 MB

Summary

Add up the maximum unit-capacity flow between every pair of junctions in a graph where each junction joins at most three pipes.

Level: Hard8 of 10
Topics: Graph, Tree, BFS, DFS
Solved: No attempts yet

Problem

You have been hired to upgrade the orange juice transport system of an old fruit processing plant. The system is made of pipes and junctions. Every pipe is bidirectional and every pipe carries at most 1 liter per second. Pipes meet at junctions, and each junction joins at most three pipes. A junction itself has unlimited capacity. Junctions are numbered with the integers from 1 to $n$ .

Before you propose an upgrade you have to analyse the current system. For two different junctions $s$ and $t$ , the $s$ - $t$ flow is the largest amount of juice, in liters per second, that can move through the system when a source is installed at junction $s$ and a sink at junction $t$ . In the system of the first sample input, the 1-6 flow is 3 and the 1-2 flow is 2.

Find the sum of the $a$ - $b$ flow over every pair of junctions $a$ and $b$ with $a < b$ .

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 3000$ , $0 \le m \le 4500$ ), the number of junctions and the number of pipes. Each of the next $m$ lines contains two different integers $a$ and $b$ ( $1 \le a, b \le n$ ) describing a pipe that connects junction $a$ and junction $b$ .

Every junction is connected to at most three other junctions. Every pair of junctions is connected by at most one pipe.

Output

Print a single integer, the sum of the $a$ - $b$ flow over every pair of junctions $a$ and $b$ with $a < b$ .

Hint

Examples2

Example 1
Input
```
6 8
1 3
2 3
4 1
5 6
2 6
5 1
6 4
5 3
```
Expected output
```
36
```
Example 2
Input
```
4 2
1 2
3 4
```
Expected output
```
2
```