407307: GYM102759 E Chemistry

Changki Yun is a professor in the Department of Chemistry, Seoul National University. To fight the ongoing COVID-19 pandemic, Changki conducts research on a certain molecule.

The molecule consists of $$$N$$$ atoms with $$$M$$$ chemical bonds, which we will simply consider as an undirected graph without self-loops or parallel edges. Note that, unlike real-life chemistry, it is not guaranteed that the molecule is connected, or that atoms in the molecule have degree at most 4.

Changki can use a machine to change the molecule. When Changki enters two integers $$$1 \le L \le R \le N$$$, the machine will keep only atoms in the range $$$L, L+1, \cdots, R$$$, as well as any bonds that were only between kept atoms.

Changki thinks that molecules which form chains are crucial to his research. A molecule forms a chain if you can place the atoms in a line such that a chemical bond between two atoms exists if and only if they are adjacent on the line. Please count the number of pairs $$$(L, R)$$$ which can be put in the machine to form a chain.

The first line contains two space-separated integers $$$N, M$$$ ($$$1 \le N \le 250\,000, 0 \le M \le 250\,000$$$).

The next $$$M$$$ lines contain two space-separated integers $$$u, v$$$ denoting that there is a chemical bond connecting vertices $$$u$$$ and $$$v$$$. ($$$1 \le u, v \le N, u \neq v$$$) There are no parallel edges.

Print the single integer denoting the answer.

3 3
1 2
2 3
3 1

5

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

17

12 12
1 2
3 4
5 6
7 8
9 10
11 12
2 4
4 6
6 8
8 10
10 12
12 2

28