Hossam makes a big party, and he will invite his friends to the party.

He has $n$ friends numbered from $1$ to $n$. They will be arranged in a queue as follows: $1, 2, 3, \ldots, n$.

Hossam has a list of $m$ pairs of his friends that don't know each other. Any pair not present in this list are friends.

A subsegment of the queue starting from the friend $a$ and ending at the friend $b$ is $[a, a + 1, a + 2, \ldots, b]$. A subsegment of the queue is called good when all pairs of that segment are friends.

Hossam wants to know how many pairs $(a, b)$ there are ($1 \le a \le b \le n$), such that the subsegment starting from the friend $a$ and ending at the friend $b$ is good.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$), the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer numbers $n$ and $m$ ($2 \le n \le 10^5$, $0 \le m \le 10^5$) representing the number of friends and the number of pairs, respectively.

The $i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i\le n$, $x_i \neq y_i$) representing a pair of Hossam's friends that don't know each other.

Note that pairs can be repeated.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $m$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print an integer — the number of good subsegments.


-----Examples-----

Input
2
3 2
1 3
2 3
4 2
1 2
2 3
Output
4
5


-----Note-----

In the first example, the answer is $4$.

The good subsegments are:

[1]

[2]

[3]

[1, 2]

In the second example, the answer is $5$.

The good subsegments are:

[1]

[2]

[3]

[4]

[3, 4]

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Amortized analysis

Constructive algorithms


Solutions:
import sys

def N():
	return int(sys.stdin.readline())

def S():
	return sys.stdin.readline().rstrip()

def L():
	return sorted(map(int, sys.stdin.readline().split()))

def M():
	return map(int, sys.stdin.readline().split())
for _ in range(N()):
	(n, m) = M()
	subsegment = list(range(1, n + 1))
	for _ in range(m):
		(x, y) = M()
		mini = min(x, y) - 1
		maxi = max(x, y) - 1
		subsegment[maxi] = min(maxi - mini, subsegment[maxi])
	for i in range(1, n):
		if subsegment[i] > subsegment[i - 1] + 1:
			subsegment[i] = subsegment[i - 1] + 1
	print(sum(subsegment))


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	(n, m) = list(map(int, sys.stdin.readline().strip().split()))
	e = [0] * n
	for i in range(0, m):
		(x, y) = list(map(int, sys.stdin.readline().strip().split()))
		if x > y:
			(x, y) = (y - 1, x - 1)
		else:
			(x, y) = (x - 1, y - 1)
		e[y] = max(e[y], x + 1)
	for i in range(1, n):
		e[i] = max(e[i], e[i - 1])
	ans = 0
	for i in range(0, n):
		ans += i - e[i] + 1
	print(ans)


t = int(input())
result = []
for i in range(t):
	(n, m) = list(map(int, input().split(' ')))
	l = [n + 1 for j in range(n + 1)]
	l[0] = 'start :'
	for j in range(m):
		xiyi = list(map(int, input().split(' ')))
		xiyi.sort()
		if xiyi[1] < l[xiyi[0]]:
			l[xiyi[0]] = xiyi[1]
	npairs = 0
	for j in range(n - 1, 1, -1):
		if l[j - 1] > l[j]:
			l[j - 1] = l[j]
		if l[j] - j - 1 > 0:
			npairs += l[j] - j - 1
	if l[1] - 2 > 0:
		npairs += l[1] - 2
	result.append(npairs + n)
for k in result:
	print(k)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0 for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		if l[b] < a:
			l[b] = a
	ans = 1
	p = 1
	for i in range(2, n + 1):
		if i - p - 1 < l[i] and (not l[i] == 0):
			p = i - l[i]
		else:
			p += 1
		ans += p
	print(ans)


from math import *
from collections import deque
from functools import lru_cache
from collections import defaultdict
MOD = 10 ** 9 + 7
from sys import stdin, stdout

def solution():
	(n, m) = map(int, input().split())
	right_most = defaultdict(lambda : n + 1)
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		right_most[a] = min(right_most[a], b)
	res = 0
	min_run = n + 1
	for i in range(1, n + 1)[::-1]:
		min_run = min(min_run, right_most[i])
		ans = min_run - i
		res += ans
	return print(res)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solution()
main()


t = int(input())
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	prev = [1] * (n + 1)
	while m > 0:
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		if x == y:
			continue
		if x > y:
			prev[x] = max(prev[x], y + 1)
		else:
			prev[y] = max(prev[y], x + 1)
		m -= 1
	ans = 0
	for i in range(1, n + 1):
		prev[i] = max(prev[i], prev[i - 1])
		ans += i - prev[i] + 1
	print(ans)
	t -= 1


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	stranger = [n] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		stranger[x] = min(stranger[x], y - 1)
	ans = 0
	p = n
	for i in range(n, 0, -1):
		p = min(p, stranger[i])
		ans += p - i + 1
	print(ans)


def b():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		adj = [i for i in range(n, 0, -1)]
		for _ in range(m):
			(x, y) = map(int, input().split())
			mi = min(x, y) - 1
			mx = max(x, y) - 1
			adj[mi] = min(adj[mi], mx - mi)
		for i in range(n - 2, -1, -1):
			if adj[i] > adj[i + 1] + 1:
				adj[i] = adj[i + 1] + 1
		print(sum(adj))
b()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = dict()
	for i in range(m):
		a = list(map(int, input().split()))
		a.sort()
		if a[1] in d:
			d[a[1]] = max(d[a[1]], a[0])
		else:
			d[a[1]] = a[0]
	ans = 0
	c = 1
	m = -1
	for i in range(1, n + 1):
		if i in d and m < d[i]:
			c = i - d[i]
			m = d[i]
		ans += c
		c += 1
	print(ans)


import sys
import threading
from functools import lru_cache
from collections import defaultdict, deque

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(i) for i in input().split()]
		mapping = [set() for i in range(n + 1)]
		for i in range(m):
			(x, y) = [int(i) for i in input().split()]
			mapping[x].add(y)
			mapping[y].add(x)
		ans = 0
		left = 1
		current = {left}
		for right in range(1, n + 1):
			current.add(right)
			while mapping[right].intersection(current):
				current.discard(left)
				left += 1
			window_size = right - left + 1
			ans += window_size
		print(ans)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	mins = [n + 1 for j in range(n)]
	for i in range(m):
		(l, r) = list(map(int, input().split()))
		if r < l:
			(l, r) = (r, l)
		j = l
		if r < mins[j - 1]:
			mins[j - 1] = r
	M = n + 1
	for i in range(n):
		k = n - 1 - i
		if mins[k] > M:
			mins[k] = M
		M = mins[k]
	answer = sum(mins) - n * (n + 1) // 2
	print(answer)


t = int(input())
for p in range(t):
	(n, m) = map(int, input().split())
	friends = [n] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		if x < y:
			friends[x] = min(friends[x], y)
		else:
			friends[y] = min(friends[y], x)
	ans = 0
	for i in range(n - 2, -1, -1):
		friends[i] = min(friends[i + 1], friends[i])
	for i in range(n):
		ans += friends[i] - i
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	MIN = [n + 1 for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		MIN[x] = min(MIN[x], y)
	for i in range(n, 1, -1):
		MIN[i - 1] = min(MIN[i - 1], MIN[i])
	ans = 0
	for i in range(1, n + 1):
		ans += MIN[i] - i
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		if x < y:
			(x, y) = (y, x)
		t.append((x, y))
	t = list(sorted(t))
	r = 0
	j = 0
	e = 0
	for i in range(1, n + 1):
		while j < m and t[j][0] == i:
			e = max(e, t[j][1])
			j += 1
		r += i - e
	print(r)


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, m) = R()
	a = [0] + [0] * n
	r = k = i = 0
	for _ in [0] * m:
		(x, y) = sorted(R())
		a[y] = max(a[y], x)
	for x in a:
		k = max(k, x)
		r += i - k
		i += 1
	print(r)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mlnf = [0] * n
	for i in range(m):
		(a, b) = map(int, input().split())
		(a, b) = (min(a, b), max(a, b) - 1)
		mlnf[b] = max(mlnf[b], a)
	ans = 0
	af = 0
	for i in range(n):
		af = max(af, mlnf[i])
		ans += i - af + 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	f = [0] * (n + 2)
	ans = 0
	sum = 0
	for _ in range(m):
		a = list(map(int, input().split(' ')))
		f[max(a)] = max(f[max(a)], min(a))
	for i in range(1, n + 1):
		ans = max(ans, f[i])
		sum += i - ans
	print(sum)


for _ in range(int(input())):
	(n, m) = [int(num) for num in input().split(' ')]
	friends = [-1] * (n + 1)
	for _ in range(m):
		(i, j) = sorted([int(num) for num in input().split(' ')])
		friends[j] = max(i + 1, friends[j])
	subsegments = 0
	j = 1
	for i in range(1, n + 1):
		while j <= n and friends[j] <= i:
			j += 1
		subsegments += j - i
		i += 1
	print(subsegments)


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	(n, m) = A()
	a = [0 for i in range(n + 1)]
	maxi = c = 0
	if 'codeforces' == 28226329:
		print('Tanmay')
	for __ in range(m):
		(x, y) = A()
		if y > x:
			a[y] = max(a[y], x)
			continue
		a[x] = max(a[x], y)
	for i in range(1, n + 1):
		maxi = max(maxi, a[i])
		a[i] = maxi
	for i in range(1, n + 1):
		c += i - a[i]
	print(c)


z = int(input())
for i in range(z):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	M = [[] for j in range(n)]
	Ma = [-1 for i in range(n)]
	for j in range(m):
		line = input().split()
		first = int(line[0]) - 1
		second = int(line[1]) - 1
		M[max(first, second)].append(min(first, second))
	for j in range(n):
		if len(M[j]) != 0:
			ma = M[j][0]
			for k in M[j]:
				if ma < k:
					ma = k
			Ma[j] = ma
	l = 0
	r = 0
	sum = 1
	while r < n - 1:
		r = r + 1
		if Ma[r] >= l:
			l = Ma[r] + 1
		sum = sum + r - l + 1
	print(sum)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().strip().split()))
	if m == 0:
		print(n * (n - 1) // 2 + n)
	else:
		dp = [float('inf')] * (n + 1)
		ans = 0
		for i in range(m):
			(a, b) = list(map(int, input().strip().split()))
			if a < b:
				dp[a] = min(dp[a], b)
			else:
				dp[b] = min(dp[b], a)
		mini = float('inf')
		for i in range(n, 0, -1):
			mini = min(dp[i], mini)
			ans += mini - i if mini != float('inf') else n - i + 1
		print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	l = list([n] * (n + 1))
	for _ in range(m):
		(x, y) = [int(x) for x in input().split()]
		(min_v, max_v) = (min(x, y), max(x, y))
		l[min_v] = min(l[min_v], max_v - 1)
	for i in range(n - 2, -1, -1):
		l[i] = min(l[i], l[i + 1])
	ans = 0
	for i in range(1, n + 1):
		ans += l[i] - i + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	enemies = []
	for _ in range(m):
		enemies.append(sorted([int(x) - 1 for x in input().split()]))
	new_left = [-1 for _ in range(n)]
	for (l, r) in enemies:
		new_left[r] = max(new_left[r], l)
	left = 0
	ssum = 0
	for i in range(n):
		left = max(left, new_left[i] + 1)
		ssum += i - left + 1
	print(ssum)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	data = {}
	for i in range(m):
		(a, b) = map(int, input().split())
		k = min(a, b)
		l = max(a, b)
		if k in data and data[k] > l:
			data[k] = l
		elif k not in data:
			data[k] = l
	total = 0
	k = n
	for j in range(1, n + 1):
		i = n + 1 - j
		if i in data:
			total += min(data[i] - i, k - i + 1)
			if k > data[i] - 1:
				k = data[i] - 1
		else:
			total += k - i + 1
	print(total)


test = int(input())
while test > 0:
	test -= 1
	(n, m) = [int(i) for i in input().split()]
	arr = [n + 1 for i in range(n + 1)]
	for i in range(m):
		edg = [int(i) for i in input().split()]
		if edg[0] < edg[1]:
			arr[edg[0]] = min(arr[edg[0]], edg[1])
		else:
			arr[edg[1]] = min(arr[edg[1]], edg[0])
	countPair = 0
	for i in range(n, 0, -1):
		countPair += arr[i] - i
		arr[i - 1] = min(arr[i - 1], arr[i])
	print(countPair)


testcase_no = int(input())
for _ in range(testcase_no):
	(n, m) = map(int, input().split())
	pairs = []
	for i in range(m):
		(L, R) = map(int, input().split())
		pairs.append((min(L, R), max(L, R)))
	pairs = sorted(pairs)
	min_Rs = [0 for j in range(n + 1)]
	minVal = 10 ** 18
	for i in range(m - 1, -1, -1):
		minVal = min(minVal, pairs[i][1])
		min_Rs[pairs[i][0]] = minVal
	min_Rs[n] = n + 1
	for i in range(n - 1, 0, -1):
		if min_Rs[i] == 0:
			min_Rs[i] = min_Rs[i + 1]
	count = 0
	for iter in range(1, n + 1):
		count += min_Rs[iter] - iter
	print(count)


def exe():
	d = {}
	arr = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		d[i] = n + 1
	for i in range(m):
		d[lst[i][0]] = min(d[lst[i][0]], lst[i][1])
	ans = 0
	mini = d[n]
	for i in range(n, 0, -1):
		mini = min(d[i], mini)
		arr[i] = mini
	for i in range(1, n + 1):
		ans += arr[i] - i
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = [sorted(list(map(int, input().split()))) for i in range(m)]
	print(exe())


t = int(input())
for x in range(t):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [0] * (n + 1)
	for i in range(m):
		(a, b) = [int(i) for i in input().split(' ')]
		arr[max(a, b)] = max(arr[max(a, b)], min(a, b))
	answer = 0
	for i in range(1, n + 1):
		arr[i] = max(arr[i], arr[i - 1])
		answer += i - arr[i]
	print(answer)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	z = list(range(1, x + 1))
	aa = [0] * (1 + x)
	for j in range(y):
		(a, b) = map(int, input().split())
		u = [a, b]
		aa[max(u)] = max(min(u), aa[max(u)])
	for k in range(1, x + 1):
		aa[k] = max(aa[k], aa[k - 1])
	print(sum(z) - sum(aa))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	nezn = [2 * 10 ** 9] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		(x, y) = (min(x, y) - 1, max(x, y) - 1)
		nezn[x] = min(y, nezn[x])
	ogr = n
	pri = -1
	ans = 0
	for i in range(n):
		if i != pri + 1 and nezn[i] == 2 * 10 ** 9:
			ans += ogr - i
		elif i == pri + 1 and nezn[i] == 2 * 10 ** 9:
			ogr = n
			j = i + 1
			while j < ogr:
				if nezn[j] <= ogr:
					ogr = min(ogr, nezn[j])
					pri = j
				j += 1
			ans += ogr - i
		elif i != pri + 1:
			ans += ogr - i
		elif i == pri + 1:
			j = i + 1
			ogr = nezn[i]
			pri = i
			while j < ogr:
				if nezn[j] <= ogr:
					ogr = min(ogr, nezn[j])
					pri = j
				j += 1
			ans += ogr - i
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	lst = [n] * n
	dct = {}
	for i in range(m):
		(a, b) = [int(x) for x in input().split()]
		min_ = min(a, b)
		max_ = max(a, b)
		dct[min_] = min(dct.get(min_, n + 1), max_)
	dct = {k: dct[k] for k in sorted(dct, reverse=True)}
	right_border = n + 1
	sum = 0
	for pos in range(n, 0, -1):
		right_border = min(dct.get(pos, n + 1), right_border)
		sum += right_border - pos
	print(sum)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [float('inf') for i in range(n + 1)]
	count = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		a[x] = min(a[x], y)
	mx = float('inf')
	for i in range(n - 1, 0, -1):
		if mx == a[i] and mx == float('inf'):
			count += n - i
		else:
			count += min(a[i], mx) - i - 1
		mx = min(a[i], mx)
	print(count + n)


t = int(input())
for test in range(t):
	www = input().split()
	n = int(www[0])
	m = int(www[1])
	starts = []
	for i in range(n + 1):
		starts.append(0)
	for i in range(m):
		vvv = input().split()
		vvv[0] = int(vvv[0])
		vvv[1] = int(vvv[1])
		vvv = sorted(vvv)
		a = vvv[0]
		b = vvv[1]
		starts[b] = max(starts[b], a)
	right = 1
	ans = 0
	for i in range(1, n + 1):
		for j in range(right + 1, n + 1):
			if i <= starts[j]:
				break
			right += 1
		if right == n + 1:
			right = n
		kk = right - i + 1
		ans += kk
	print(ans)


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n, m) = inp_arr()
	a = []
	for i in range(m):
		(x, y) = inp_arr()
		temp = min(x, y)
		y = max(x, y)
		x = temp
		a.append([x, y])
	mp = collections.defaultdict(list)
	a.sort()
	for x in a:
		mp[x[0]].append(x[1])
	ans = 0
	new_a = []
	for x in mp:
		new_a.append([x, mp[x][0]])
	new_a.sort(key=lambda x: x[1])
	need = 1
	for x in new_a:
		y = x[1]
		while need <= x[0]:
			ans += y - need
			need += 1
	diff = n - need + 1
	print(ans + diff * (diff + 1) // 2)
(tt,) = inp_arr()
for t in range(tt):
	solve()


t = int(input())
while t:
	(n, m) = map(int, input().split())
	if m == 0:
		print(int(n * (n + 1) / 2))
		t -= 1
		continue
	queries = []
	for j in range(m):
		(a, b) = map(int, input().split())
		queries.append([min(a, b), max(a, b)])
	ans = [n for u in range(n + 1)]
	uniqq = []
	queries.sort()
	for i in range(m):
		if i != 0 and queries[i][0] != queries[i - 1][0]:
			uniqq.append(queries[i])
		if i == 0:
			uniqq.append(queries[i])
	l = len(uniqq)
	uptr = l - 1
	for person in range(n, 0, -1):
		while uptr > 0 and uniqq[uptr][0] > person:
			uptr -= 1
		if uniqq[uptr][0] == person:
			if person != n:
				ans[person] = min(ans[person + 1], uniqq[uptr][1] - 1)
			else:
				ans[person] = uniqq[uptr][1] - 1
		elif person != n:
			ans[person] = ans[person + 1]
	res = 0
	for k in range(1, n + 1):
		res += ans[k] - k + 1
	print(res)
	t -= 1


import sys
import re
import math
from math import log2
from math import log
from math import ceil
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	line = get()
	(m, k) = (line[0], line[1])
	dd = {}
	for j in range(k):
		line = get()
		(a, b) = (line[0], line[1])
		(c, d) = (min(a, b), max(a, b))
		if c not in dd:
			dd[c] = d
		dd[c] = min(dd[c], d)
	total = 0
	ends = [m + 1 for j in range(m + 1)]
	smallest = m + 1
	for j in range(m, 0, -1):
		if j in dd:
			smallest = min(smallest, dd[j])
		ends[j] = smallest
	for j in range(1, m + 1):
		total += ends[j] - j
	print(total)


N = int(input())
for i in range(N):
	num = list(map(eval, input().split()))
	flag = [10000000.0 for i in range(num[0] + 1)]
	tmp = []
	for j in range(num[1]):
		tmp.append(list(map(eval, input().split())))
	for j in range(num[1]):
		(a, b) = (tmp[j][0], tmp[j][1])
		if a > b:
			(a, b) = (b, a)
		flag[a] = min(b, flag[a])
	l = r = num[0]
	ans = 0
	while l > 0:
		r = min(r, flag[l] - 1)
		ans += r - l + 1
		l -= 1
	print(ans)


N = int(input())
for i in range(N):
	num = list(map(eval, input().split()))
	flag = [10000000.0 for i in range(num[0] + 1)]
	tmp = []
	for j in range(num[1]):
		tmp.append(list(map(eval, input().split())))
	for j in range(num[1]):
		if tmp[j][0] < flag[tmp[j][1]] and tmp[j][0] > tmp[j][1]:
			flag[tmp[j][1]] = tmp[j][0]
		if tmp[j][1] < flag[tmp[j][0]] and tmp[j][1] > tmp[j][0]:
			flag[tmp[j][0]] = tmp[j][1]
	l = r = num[0]
	ans = 0
	while l > 0:
		if flag[l] < l or flag[l] == 10000000.0:
			ans += r - l + 1
		else:
			r = min(r, flag[l] - 1)
			ans += r - l + 1
		l -= 1
	print(ans)