Juice Junctions

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

Hard8GraphTreeBFSDFSNo attempts yetTime limit7sMemory limit512 MB

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 nn.

Before you propose an upgrade you have to analyse the current system. For two different junctions ss and tt, the ss-tt flow is the largest amount of juice, in liters per second, that can move through the system when a source is installed at junction ss and a sink at junction tt. 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 aa-bb flow over every pair of junctions aa and bb with a<ba < b.

Input

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

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 aa-bb flow over every pair of junctions aa and bb with a<ba < b.

Hint