Building a Linear Molecule

Lev received a molecule as a material for a chemistry experiment. The molecule has $N$ atoms, numbered from 1 to $N$ with distinct labels, and $M$ distinct chemical bonds. Each bond joins two different atoms, so the molecule can be treated as an undirected graph. Unlike real chemistry, the molecule does not have to be connected, does not have to consist of two or more atoms, and an atom may not be linked to four or fewer other atoms.

Lev uses a state-of-the-art machine for the experiment. When Lev enters two integers $1 \le L \le R \le N$, the machine removes every atom except the atoms numbered from $L$ to $R$, inclusive. Removing atom $x$ means removing atom $x$ together with all bonds attached to it.

Lev must record the resulting molecule in a report, and the molecule in the report must be linear. That is, the atoms can be rearranged along a straight line so that adjacent atoms are bonded to each other and non-adjacent atoms have no bond between them.

A skilled chemist, Lev can make many such molecules. For extra credit, Lev also wants to report how many distinct linear molecules can be made. Lev needs the number of integer pairs $(L, R)$ that can be entered into the machine to produce a linear molecule. Write a program that counts these pairs.

The first line contains two integers $N$ and $M$, separated by a space. $N$ is the number of atoms in the molecule, and $M$ is the number of chemical bonds.

Each of the next $M$ lines contains two integers $A_i$ and $B_i$, separated by a space. This means there is a chemical bond between atom $A_i$ and atom $B_i$. The line numbers are $(i+1)$ for $i$ from 1 to $M$.