CF1599I 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$ 组成的无向图是 “沙漠” 。

无

无

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.