Hossam 与朋友们

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

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$ 行，每行包含两个整数 $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

数据范围

对于所有数据，$1\le t\le2\times10^4$，$2\le n\le10^5$，$0\le m\le10^5$；所有测试用例中 $n$ 与 $m$ 的总和分别不超过 $10^5$。禁配对允许重复。