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.

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.

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.