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]