Гра-гра-граф

Як ми всі знаємо, щоб пройти на фінальний етап олімпіади недостатньо здати всі задачі, треба ще перемогти Антона. Він має улюблену гру, в яку грає з кожним. Гра відбувається на неорієнтованому графі. Гравці ходять по черзі та Антон ходить першим. На кожному кроці гравці можуть зробити одне з наступного:

• Вибрати дві вершинки $u$ та $v$, між якими є ребро, та видалити його

• Вибрати дві вершинки $u$ та $v$, між якими нема ребра, та додати його

Перший гравець перемагає, якщо в будь-який момент гри не можна більше додати ребра в граф. Другий гравець перемагає, якщо за $10^{100}$ ходів не переміг перший гравець.

Вам дано неорієнтований граф на $n$ вершинах з $m$ ребрами. Назвемо підгрою на відрізку $[l;r]$ гру, яка відбувається враховуючи тільки вершини з номерами на відрізку $[l;r]$. Порахуйте кількість підігор де перемагає перший гравець по всім парам $[l;r]$ ($1\le l\le r\le n$).

Input

Перший рядок містить два цілі числа $n$ ($1\le n\le 10^6$) та $m$ ($1\le m\le 10^6$) — кількість вершин та кількість ребер відповідно.

Наступні $m$ рядків містять два цілі числа $u$ та $v$ ($1\le u,v\le n$) — опис ребер графа.

Граф не містить петлі та кратні ребра.

Output

Виведіть одне ціле число — відповідь на задачу.

Examples

Note

Пояснення до другого прикладу:

Підгра на відрізку $[1;1]$ є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу.

Підгра на відрізку $[1;3]$ є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу.

Підгра на відрізку $[4;5]$ є виграшною для першого гравця, тому що на першому кроці перший гравець додає ребро $(4;5)$ і отримує граф, до якого більше не можна додавати ребра.

Можна показати, що підгра на відрізку $[1;4]$ є програшною для першого гравця.

Граф у другому прикладі