Gra-gra-graph#179
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 and with an edge between them and remove it.
Choose two vertices and 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 vertices with 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).
The first line contains two integers (1 \le n \le 10^6) and (1 \le m \le 10^6) — the number of vertices and edges, respectively.
The next lines contain two integers and (1 \le u,v \le n) — the description of the graph edges.
The graph does not contain loops or multiple edges.
Output a single integer — the answer to the problem.
Example 1
Example 2
Explanation for the second example:
The subgame on the segment 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 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 is winning for the first player, because on the first move the first player adds the edge and obtains a graph to which no more edges can be added.
It can be shown that the subgame on the segment is losing for the first player.
The graph in the second example