5-5 Hossam and Friends

5-5 Hossam and Friends

Hossam and Friends

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

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

题目描述

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

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

霍萨姆有一个mm对不认识的朋友的名单。任何没有出现在这个列表中的一对都是朋友。

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

Hossam想知道有多少对(a,b)(a, b)1abn1 \le a \le b \le n),使得从朋友aa开始,在朋友bb结束的子段是好的。

输入

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

每个测试案例的第一行包含两个整数nnmm2n1052 \le n \le 10^50m1050 \le m \le 10^5),分别代表朋友的数量和配对的数量。

接下来的mm行包含两个整数xix_iyiy_i1xi,yin1 \le x_i, y_i\le nxiyix_i \neq y_i),代表霍萨姆的一对不认识的朋友。

请注意,一个数据对 <xi,yi><x_i, y_i>可以重复。

保证所有测试案例的nn之和不超过10510^5,所有测试案例的mm之和不超过10510^5

输出

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

样例

输入样例

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

输出样例

4
5

样例解释

在第一个例子中,答案是44

好的字段分别为:

[1]

[2]

[3]

[1, 2]

在第二个例子中,答案是55

好的字段分别为:

[1]

[2]

[3]

[4]

[3, 4]

信息

ID
1467
难度
9
分类
(无)
标签
(无)
递交数
9
已通过
5
通过率
56%
上传者

相关