19854번 - 직선형 분자 만들기

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

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

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

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

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

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

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

• 1 ≤ N ≤ 250,000
• 0 ≤ M ≤ 250,000
• 1 ≤ A_i, B_i ≤ N, A_i ≠ B_i, i ≠ j에 대해 {A_i, B_i} ≠ {A_j, B_j}