给你一个由 $$$N$$$ 节点和 $$$M$$$ 边、$$$E_1、E_2、\dots E_M$$$ 组成的无向图。
如果连通图的每条边最多属于一个简单循环,则该图是一棵仙人掌。如果图的每个连接组件都是仙人掌,那么图就是沙漠。
求 $$$(L, R)$$$, ($$$1 \leq L \leq R \leq M$$$) 对的数量,这样,如果我们删除除 $$$E_L, E_{L+1}, \dots E_R$$$ 之外的所有边,则该图是沙漠。
输入
第一行包含两个整数 $$$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$$$。
输出
输出包含一个整数——答案。
示例
输入 #1
5 6 1 2 2 3 3 4 4 5 5 1 2 4
输出 #1
20
输入 #2
2 3 1 2 1 2 1 2
输出 #2
5
注意
在第二个示例中:$$$(1, 1)$$$、$$$(2, 2)$$$ 和 $$$(3, 3)$$$ 的图是沙漠,因为它们没有任何循环。 $$$(1, 2)$$$ 和 $$$(2, 3)$$$ 对的图有一个长度为 2 的循环,因此它们是沙漠。