407307: GYM102759 E Chemistry
Description
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.
InputThe 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.
OutputPrint the single integer denoting the answer.
ExamplesInput3 3 1 2 2 3 3 1Output
5Input
8 7 2 1 1 4 4 3 3 8 8 7 7 5 5 6Output
17Input
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 2Output
28