Як ми всі знаємо, щоб пройти на фінальний етап олімпіади недостатньо здати всі задачі, треба ще перемогти Антона. Він має улюблену гру, в яку грає з кожним. Гра відбувається на неорієнтованому графі. Гравці ходять по черзі та Антон ходить першим. На кожному кроці гравці можуть зробити одне з наступного:
Вибрати дві вершинки u та v, між якими є ребро, та видалити його
Вибрати дві вершинки u та v, між якими нема ребра, та додати його
Перший гравець перемагає, якщо в будь-який момент гри не можна більше додати ребра в граф. Другий гравець перемагає, якщо за 10100 ходів не переміг перший гравець.
Вам дано неорієнтований граф на n вершинах з m ребрами. Назвемо підгрою на відрізку [l;r] гру, яка відбувається враховуючи тільки вершини з номерами на відрізку [l;r]. Порахуйте кількість підігор де перемагає перший гравець по всім парам [l;r] (1≤l≤r≤n).
Перший рядок містить два цілі числа n (1≤n≤106) та m (1≤m≤106) — кількість вершин та кількість ребер відповідно.
Наступні m рядків містять два цілі числа u та v (1≤u,v≤n) — опис ребер графа.
Граф не містить петлі та кратні ребра.
Виведіть одне ціле число — відповідь на задачу.
Пояснення до другого прикладу:
Підгра на відрізку [1;1] є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу.
Підгра на відрізку [1;3] є виграшною для першого гравця, тому що до першого кроку вже не можна додати більше ребер до графу.
Підгра на відрізку [4;5] є виграшною для першого гравця, тому що на першому кроці перший гравець додає ребро (4;5) і отримує граф, до якого більше не можна додавати ребра.
Можна показати, що підгра на відрізку [1;4] є програшною для першого гравця.
Граф у другому прикладі