직선형 분자 만들기

레프는 화학실험 시간에 실험 재료로 분자를 받았다. 분자를 구성하는 원자는 총 $N$개이며 1번부터 $N$번까지 서로 다른 번호가 붙어 있다. 원자를 잇는 화학 결합은 총 $M$개이고, 각 결합은 서로 다른 두 원자를 연결한다. 분자는 방향이 없는 그래프로 볼 수 있다. 실제 화학의 예와 달리, 분자가 반드시 연결되어 있을 필요는 없고, 원자가 2개 이상일 필요도 없으며, 4개 이하의 다른 원자와만 연결되어 있지 않아도 된다.

레프는 실험을 위해 최첨단 기계를 사용한다. 레프가 두 정수 $1 \le L \le R \le N$을 기계에 입력하면, 기계는 번호가 $L$ 이상 $R$ 이하인 원자를 제외한 다른 모든 원자를 제거한다. $x$번 원자를 제거한다는 것은 $x$번 원자와 이 원자에 연결된 화학 결합을 모두 제거하는 것이다.

레프는 이렇게 만든 분자를 보고서에 적어야 하며, 보고서에 적을 분자는 직선형이어야 한다. 즉, 직선 위에 원자들을 적당히 재배치하여 인접한 원자끼리는 모두 화학 결합으로 이어지고, 인접하지 않은 원자끼리는 결합이 없도록 할 수 있어야 한다.

숙련된 화학도인 레프는 이런 분자를 얼마든지 많이 만들 수 있다. 하지만 보고서의 추가 점수를 받기 위해, 만들 수 있는 직선형 분자가 총 몇 가지인지도 적으려고 한다. 즉, 레프는 직선형 분자를 만들기 위해 실험 기계에 입력할 수 있는 정수 쌍 $(L, R)$의 개수를 알고 싶다. 레프를 위해 가능한 분자의 개수를 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 $N$과 $M$이 공백을 사이에 두고 주어진다. 분자에 포함된 원자의 개수가 $N$개이고, 화학 결합의 개수가 $M$개라는 뜻이다.

둘째 줄부터 $M$개의 줄에 걸쳐 화학 결합 정보가 주어진다. $(i+1)$번째 줄에는 두 정수 $A_i$와 $B_i$가 공백을 사이에 두고 주어지며, 이는 $A_i$번 원자와 $B_i$번 원자를 잇는 화학 결합이 존재한다는 뜻이다.