Graph-Graph-Graph#11361
As we all know, to advance to the final stage of the olympiad, it's 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, and Anton goes first. On each turn, a player can do one of the following:
Choose two vertices and that are connected by an edge, and remove it
Choose two vertices and that are not connected by an edge, and add it
The first player wins if at any moment during the game no more edges can be added to the graph. The second player wins if the first player has not won after 10^{100} moves.
You are given an undirected graph with vertices and edges. Let's call a subgame on the segment [l;r] a game that takes place considering only vertices with numbers in the segment [l;r]. Count 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 the number of edges respectively.
The next lines contain two integers and (1 \le u,v \le n) — the description of the edges of the graph.
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 before the first move, no more edges can be added to the graph.
The subgame on the segment is winning for the first player because before the first move, no more edges can be added to the graph.
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.
Graph in the second example