题目描述

There are $n$ people standing in a line, numbered from $1$ to $n$ from left to right. Among these people, there are $m$ pairs of friends. Define an interval $[l,r]$ ($1 \leq l \leq r \leq n$) as friendly if and only if every pair of people within the interval are friends. How many friendly intervals are there?官方中文

输入格式

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^6$), representing the number of people and the number of pairs of friends, respectively. The next $m$ lines each contain two integers $u$ and $v$ ($1 \leq u < v \leq n$), representing a pair of friends. It is guaranteed that there are no duplicate friend pairs in the input.官方中文

输出格式

Output a single integer representing the number of friendly intervals.