시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 (추가 시간 없음) 1024 MB78231324.074%

문제

레프는 화학실험 시간에 실험 재료로 분자를 받았다. 분자를 구성하는 원자는 총 N개로 1번부터 N번까지 서로 다른 번호가 붙어 있고, 두 원자를 연결하는 총 M개의 서로 다른 화학 결합이 존재한다. 각 결합은 서로 다른 두 원자를 연결한다. 즉, 분자는 방향성이 없는 그래프로 생각할 수 있다. 실제 화학에서의 예시와 다르게, 분자가 꼭 연결되어 있거나, 2개 이상의 원자로 이루어져 있거나, 4개 이하의 다른 원자와 연결되어 있지는 않을 수 있음에 주의하라.

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

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

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

입력

입력의 첫째 줄에는 두 정수 N, M이 공백을 사이에 두고 주어진다. 분자에 포함되는 원자의 개수가 N개이고, 화학 결합의 개수가 M개임을 의미한다.

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

출력

첫째 줄에 실험 기계에 입력할 수 있는 정수 쌍의 개수를 출력한다.

제한

  • 1 ≤ N ≤ 250,000
  • 0 ≤ M ≤ 250,000
  • 1 ≤ Ai, BiN, AiBi, ij에 대해 {Ai, Bi} ≠ {Aj, Bj}

예제 입력 1

3 3
1 2
2 3
3 1

예제 출력 1

5

가능한 (L, R) 쌍은 (1, 1), (1, 2), (2, 2), (2, 3), (3, 3)이다. (1, 3)의 경우, 어떻게 배치해도 인접하지 않은 원자 간의 결합이 존재하게 된다.

예제 입력 2

8 7
2 1
1 4
4 3
3 8
8 7
7 5
5 6

예제 출력 2

17

예제 입력 3

12 12
1 2
3 4
5 6
7 8
9 10
11 12
2 4
4 6
6 8
8 10
10 12
12 2

예제 출력 3

28

벤젠 분자이다. 1개, 2개, 3개, 4개의 원자만 남길 수 있는 경우의 수는 각각 12가지, 6가지, 5가지, 5가지이다.