← 返回题目列表

Codeforces · 1599/I

I. 沙漠

中文机器翻译题面 查看原题

给你一个由 $$$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 的循环,因此它们是沙漠。