Desert

### 题目描述 众所周知，一个无向图是仙人掌图当且仅当每条无向边至多属于一个环 。特别的，只有一个点的图也是仙人掌图 。 如果无向图的每一个连通块都是一个仙人掌图，那么我们称这个图是 “沙漠” 。( 类比树和森林之间的关系 ) 给定一个 $N$ 个点 $M$ 条边的无向图，边的编号分别为 $E_1,E_2…E_M$ 。 求数字对 $(L,R)$ 的个数 ，$(1\leq L\leq R\leq M)$，使得只由 $E_L,E_{L+1}…E_R$ 组成的无向图是 “沙漠” 。 ### 输入格式 第一行包含两个整数 $N$ 和 $M$ $(2\leq N\leq 2.5\times 10^5,1\leq M \leq 5\times 10^5)$ 。 接下来 $M$ 行，每行两个整数 $u_i,v_i$，表示一条边，其中 $E_i=(u_i,v_i)$，输入保证不存在自环 。 ### 输出格式 一行一个整数，表示问题的答案 。

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.

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 $ .

The output contains one integer number – the answer.

5 6
1 2
2 3
3 4
4 5
5 1
2 4

20

2 3
1 2
1 2
1 2

5

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.