CF1771B Hossam and Friends

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$。

对于每组测试数据，输出一个整数，表示好子区间的数量。

在第一个样例中，答案是 $4$。 好子区间为： \[1\] \[2\] \[3\] \[1, 2\] 在第二个样例中，答案是 $5$。 好子区间为： \[1\] \[2\] \[3\] \[4\] \[3, 4\] 由 ChatGPT 4.1 翻译