CF1599I.Desert

You are given an undirected graph of $N$ nodes and $M$ edges, $E_1, E_2, \dots E_M$.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus.

Find the number of pairs $(L, R)$, ($1 \leq L \leq R \leq M$) such that, if we delete all the edges except for $E_L, E_{L+1}, \dots E_R$, the graph is a desert.

给你一个包含 $N$ 个节点和 $M$ 条边 $E_1, E_2, \dots, E_M$ 的无向图。

若一个连通图的每条边至多属于一个简单环，则该图称为仙人掌图（cactus）。若一个图的每个连通分量均为仙人掌图，则该图称为沙漠图（desert）。

请你计算满足如下条件的数对 $(L, R)$（其中 $1 \leq L \leq R \leq M$）的个数：仅保留边集 $\{E_L, E_{L+1}, \dots, E_R\}$，所得到的图是一个沙漠图。

The first line contains two integers $N$ and $M$ ($2 \leq N \leq 2.5 \times 10^5$, $1 \leq M \leq 5 \times 10^5$). Each of the next $M$ lines contains two integers. The $i$-th line describes the $i$-th edge. It contains integers $U_i$ and $V_i$, the nodes connected by the $i$-th edge ($E_i=(U_i, V_i)$). It is guaranteed that $1 \leq U_i, V_i \leq N$ and $U_i \neq V_i$.

第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 2.5 \times 10^5$，$1 \leq M \leq 5 \times 10^5$）。接下来的 $M$ 行每行包含两个整数。第 $i$ 行描述第 $i$ 条边，包含整数 $U_i$ 和 $V_i$，表示第 $i$ 条边所连接的两个节点（即 $E_i=(U_i, V_i)$）。保证 $1 \leq U_i, V_i \leq N$ 且 $U_i \neq V_i$。

The output contains one integer number – the answer.

输出包含一个整数——答案。

In the second example: Graphs for pairs $(1, 1)$, $(2, 2)$ and $(3, 3)$ are deserts because they don't have any cycles. Graphs for pairs $(1, 2)$ and $(2, 3)$ have one cycle of length 2 so they are deserts.

在第二个例子中：对 $(1, 1)$、$(2, 2)$ 和 $(3, 3)$ 的图是荒漠图，因为它们不含任何环；对 $(1, 2)$ 和 $(2, 3)$ 的图各含一个长度为 $2$ 的环，因此它们也是荒漠图。