Хоссам устраивает большую вечеринку, он собирается пригласить на нее своих друзей.
У него есть \(n\) друзей, пронумерованных от \(1\) до \(n\). Они будут организованы в очередь следующим образом: \(1, 2, 3, \ldots, n\).
У Хоссама есть список из \(m\) пар его друзей, которые не знакомы друг с другом. Любая пара, не входящая в этот список, знакома друг с другом.
Подотрезок очереди, начинающийся с друга \(a\) и заканчивающийся другом \(b\), равен \([a, a + 1, a + 2, \ldots, b]\). Подоторезок очереди считается хорошим, если любая пара из этого подотрезка знакома друг с другом.
Хоссам хочешь знать, сколько пар \((a, b)\) (\(1 \le a \le b \le n\)), таких, что подотрезок начинающийся с друга \(a\) и заканчивающийся другом \(b\) хороший.
Примечание
В первом наборе ответ равен \(4\). Хорошие подотрезки здесь:
[1]
[2]
[3]
[1, 2]
Во втором наборе ответ равен \(5\). Хорошие подотрезки здесь:
[1]
[2]
[3]
[4]
[3, 4]