Triangle Counting

You are given a tournament graph (a complete directed graph) of $N$ vertices, numbered from $1$ to $N$. Initially, all edges are directed towards the vertex with the higher number.

A triangle is a triplet of vertices $(a, b, c)$, such that there are edges $a \rightarrow b$, $b \rightarrow c$, $c \rightarrow a$ in the graph,
with $1 \leq a, b, c \leq N$ and $a \neq b$, $a \neq c$, $b \neq c$.

You need to process $Q$ updates, where in each update we flip an edge. The updates are permanent, and you are required to count the number of triangles in the graph following each update.

Input data

The first line of the input contains $N$ and $Q$, representing the number of vertices in the graph and the number of updates.
The next $Q$ lines contain the updates in the form $(X_i, Y_i)$, meaning that the edge between $X_i$ and $Y_i$ is to be flipped. It is guaranteed that the edge between $X_i$ and $Y_i$ in the graph is directed towards $Y_i$ right before the update.

Output data

The output must contain $Q$ lines, the number of triangles after each update.

Constraints and clarifications

• $3 \leq N \leq 200 \ 000$.
• $1 \leq Q \leq 1 \ 000 \ 000$.
• $1 \leq X_i, Y_i \leq N$ and $X_i \neq Y_i$ for each $i = 0 . . . Q − 1$.

Example

stdin

4 4
2 4
1 2
4 2
2 3

stdout

1
2
0
1

Explanation

In the sample case, the initial graph (without updates) is diplayed in the figure below.

The first update flips edge $2 \rightarrow 4$. The resulting graph contains only one triangle $2 \rightarrow 3 \rightarrow 4$ (see below).

The graphs obtained after each remaining update are displayed in the following figure (from left to right).