5-5 Hossam and Friends

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Hossam and Friends

链接:https://codeforces.com/problemset/problem/1771/B
来源:codeforces

时间限制:2 seconds
空间限制:256 megabytes

题目描述

霍萨姆搞了一个大聚会,他将邀请他的朋友们参加聚会。

他有\(n\)个朋友,编号从\(1\)到\(n\)。他们将被安排在一个队列中,情况如下:\(1, 2, 3, \ldots, n\).

霍萨姆有一个\(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\)行包含两个整数\(x_i\)和\(y_i\)(\(1 \le x_i, y_i\le n\),\(x_i \neq y_i\)),代表霍萨姆的一对不认识的朋友。

请注意,一个数据对 \(<x_i, y_i>\)可以重复。

保证所有测试案例的\(n\)之和不超过\(10^5\),所有测试案例的\(m\)之和不超过\(10^5\)。

输出

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

样例

输入样例

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

输出样例

4
5

样例解释

在第一个例子中,答案是\(4\)。

好的字段分别为:

[1]

[2]

[3]

[1, 2]

在第二个例子中,答案是\(5\)。

好的字段分别为:

[1]

[2]

[3]

[4]

[3, 4]

2023暑假集训7月10日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-10 09:00
结束于
2023-07-10 11:30
持续时间
2.5 小时
主持人
参赛人数
20