Як ми всі знаємо, щоб пройти на фінальний етап олімпіади недостатньо здати всі задачі, треба ще перемогти Антона. Він має улюблену гру, в яку грає з кожним. Гра відбувається на неорієнтованому графі. Гравці ходять по черзі та Антон ходить першим. На кожному кроці гравці можуть зробити одне з наступного: \begin{itemize} \item Вибрати дві вершинки $u$ та $v$, між якими є ребро, та видалити його \item Вибрати дві вершинки $u$ та $v$, між якими нема ребра, та додати його \end{itemize} Перший гравець перемагає, якщо в будь-який момент гри не можна більше додати ребра в граф. Другий гравець перемагає, якщо за $10^{100}$ ходів не переміг перший гравець. Вам дано неорієнтований граф на $n$ вершинах з $m$ ребрами. Назвемо підгрою на відрізку $[l;r]$ гру, яка відбувається враховуючи тільки вершини з номерами на відрізку $[l;r]$. Порахуйте кількість підігор де перемагає перший гравець по всім парам $[l;r]$ ($1 \le l \le r \le n$). \InputFile Перший рядок містить два цілі числа $n$ ($1 \le n \le 10^6$) та $m$ ($1 \le m \le 10^6$) --- кількість вершин та кількість ребер відповідно. Наступні $m$ рядків містять два цілі числа $u$ та $v$ ($1 \le u,v \le n$) --- опис ребер графа. Граф \textbf{не містить} петлі та кратні ребра. \OutputFile Виведіть одне ціле число --- відповідь на задачу. \Note Пояснення до другого прикладу: Підгра на відрізку $[1;1]$ є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу. Підгра на відрізку $[1;3]$ є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу. Підгра на відрізку $[4;5]$ є виграшною для першого гравця, тому що на першому кроці перший гравець додає ребро $(4;5)$ і отримує граф, до якого більше не можна додавати ребра. Можна показати, що підгра на відрізку $[1;4]$ є програшною для першого гравця. \begin{center} \includegraphics{https://static.eolymp.com/content/s0/s0608qopft27b8pagvc2r1i36c.png} \small{Граф у другому прикладі} \end{center}