← 返回题目列表

Codeforces · 1771/B

B. 霍萨姆和朋友们

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

Hossam 举办了一场盛大的聚会,他将邀请他的朋友参加聚会。

他有 $$$n$$$ 个朋友,编号从 $$$1$$$ 到 $$$n$$$。它们将按如下方式排列在队列中:$$$1, 2, 3, \ldots, n$$$。

Hossam 有一张他的 $$$m$$$ 不认识朋友的列表。任何未出现在该列表中的配对都是朋友。

从朋友 $$$a$$$ 开始到朋友 $$$b$$$ 结束的队列子段是 $$$[a, a + 1, a + 2, \ldots, b]$$$。当队列的所有子段都是朋友时,该子段被称为良好。

Hossam 想知道有多少对 $$$(a, b)$$$ ($$$1 \le a \le b \le n$$$),这样从朋友 $$$a$$$ 开始到朋友 $$$b$$$ 结束的子段是好的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$),测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$),分别代表朋友的数量和配对的数量。

接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$),代表 Hossam 的一对互相不认识的朋友。

请注意,配对可以重复。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$m$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 良好子段的数量。

示例

输入 #1

2
3 2
1 3
2 3
4 2
1 2
2 3

输出 #1

4
5

注意

在第一个示例中,答案是 $$$4$$$。

好的细分是:

[1]

[2]

[3]

[1, 2]

在第二个示例中,答案是 $$$5$$$。

好的细分是:

[1]

[2]

[3]

[4]

[3, 4]