Changki Yun 是首尔大学化学系的一名教授。为了抗击新冠疫情（COVID-19），Changki 正在研究某种分子。

该分子由 $N$ 个原子和 $M$ 个化学键组成，我们可以将其简单地视为一个无向图，且没有自环或重边。请注意，与现实中的化学不同，该分子不保证是连通的，也不保证每个原子的度数不超过 4。

Changki 可以使用一台机器来改变分子。当 Changki 输入两个整数 $1 \le L \le R \le N$ 时，机器将仅保留编号在 $L, L+1, \dots, R$ 范围内的原子，以及仅存在于这些被保留原子之间的化学键。

Changki 认为形成链状的分子对他的研究至关重要。如果一个分子可以将原子排成一行，使得两个原子之间存在化学键当且仅当它们在这一行中相邻，则称该分子形成了一条链。请计算有多少对 $(L, R)$ 可以放入机器中形成一条链。

输入格式

第一行包含两个空格分隔的整数 $N, M$ ($1 \le N \le 250\,000, 0 \le M \le 250\,000$)。

接下来的 $M$ 行，每行包含两个空格分隔的整数 $u, v$，表示连接顶点 $u$ 和 $v$ 的化学键 ($1 \le u, v \le N, u \neq v$)。图中不存在重边。

输出格式

输出一个整数，表示答案。

样例

样例输入 1

3 3
1 2
2 3
3 1

样例输出 1

5

样例输入 2

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

样例输出 2

17

样例输入 3

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

样例输出 3

28