Gra-gra-graph

As we all know, in order to get to the final stage of the Olympiad, it is not enough to solve all the problems, you also need to defeat Anton. He has a favorite game that he plays with everyone. The game takes place on an undirected graph. Players take turns, with Anton going first. At each step, players can do one of the following:

• Choose two vertices $u$ and $v$ with an edge between them and remove it.

• Choose two vertices $u$ and $v$ without an edge between them and add it.

The first player wins if no more edges can be added to the graph at any point in the game. The second player wins if the first player has not won within $10^{100}$ moves.

You are given an undirected graph on $n$ vertices with $m$ edges. Let a subgame on the segment $[l;r]$ be a game that takes into account only the vertices numbered on the segment $[l;r]$. Calculate the number of subgames where the first player wins for all pairs $[l;r]$ ($1\le l\le r\le n$).

Input

The first line contains two integers $n$ ($1\le n\le 10^6$) and $m$ ($1\le m\le 10^6$) — the number of vertices and edges, respectively.

The next $m$ lines contain two integers $u$ and $v$ ($1\le u,v\le n$) — the description of the graph edges.

The graph does not contain loops or multiple edges.

Output

Output a single integer — the answer to the problem.

Examples

Note

Explanation for the second example:

The subgame on the segment $[1;1]$ is winning for the first player, because no more edges can be added to the graph before the first move.

The subgame on the segment $[1;3]$ is winning for the first player, because no more edges can be added to the graph before the first move.

The subgame on the segment $[4;5]$ is winning for the first player, because on the first move the first player adds the edge $(4;5)$ and obtains a graph to which no more edges can be added.

It can be shown that the subgame on the segment $[1;4]$ is losing for the first player.

The graph in the second example