Count Valid Sequences

Given n and several forbidden pairs, the two numbers of a forbidden pair cannot appear in the same sequence. Among the sequences formed by consecutive integers from 1..n (that is, intervals [l,r] of length at least 1), count how many do not contain both numbers of any forbidden pair.

输入格式

The first line contains two integers n and m; then m lines follow, each with two integers a, b denoting a forbidden pair (in any order, possibly repeated). 1≤n≤200000, 0≤m≤200000, 1≤a,b≤n, a≠b.

输出格式

Output a single integer, the number of valid sequences.

样例 1

输入：

4 1
1 3

输出：

8

样例 2

输入：

3 0

输出：

6

样例 3

输入：

3 1
3 2

输出：

4

样例说明

Example 1: n=4, with the forbidden pair (1,3). The valid sequences are (1), (2), (3), (4), (1,2), (2,3), (3,4), (2,3,4), for 8 in total; (1,2,3) and (1,2,3,4) contain both 1 and 3, so they are invalid. Example 2: with no forbidden pairs, 3 numbers have 6 contiguous segments. Example 3: the forbidden pairs (3,2) and (2,3) are the same; only (2,3) and (1,2,3) are invalid, so the answer is 4.