408358: GYM103104 I Sequence

Nakisa likes sequence. She is interested in sequence $$$P$$$ which meets the following conditions:

• Lenth of $$$P$$$ is $$$N$$$ and the index is from $$$1$$$ to $$$N$$$.
• $$$\forall P_i \in [1,N]$$$ .
• There exists some restrictions $$$(index,value)$$$ , indicating that $$$P_{index}$$$ cannot be $$$value$$$ ($$$1 \le index,value \le N$$$) .

Nakisa does not care sequence itself, he only wants to know how many ordered tuples $$$(A,B,L,R)$$$ satisfies $$$\forall i \in[A,B]$$$ , $$$P_i$$$ can be any number in $$$[L,R]$$$ , ($$$1 \le A,B,L,R \le N$$$ , $$$A \le B$$$ and $$$L \le R$$$).

For example, $$$N=2$$$, one restriction is $$$P_2$$$ cannot be $$$1$$$. There are 5 vaild tuples, and they are as the follows:

• $$$(1,1,1,1)$$$
• $$$(1,1,1,2)$$$
• $$$(1,1,2,2)$$$
• $$$(1,2,2,2)$$$
• $$$(2,2,2,2)$$$

An invaild tuple is $$$(2,2,1,1)$$$ because $$$P_2$$$ cannot be $$$1$$$.

First line contains two numbers $$$N$$$ ($$$1 \le N \le 5000$$$) and $$$M$$$ ($$$0 \le M \le 1000000$$$). Indicatiing the lenth of the sequence and the number of restrictions.

In the following $$$M$$$ lines, each line contains two number $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le N$$$). Indicating a restriction that $$$P_a$$$ cannot be $$$b$$$.

One number indicating the answer.

2 1
2 1

5

3 5
1 1
2 1
3 1
3 2
3 3

9

• Attention that there may be some same restrictions.
• You are supposed to use faster IO method like scanf in C/C++ due to the huge amount of input.