Гра-гра-граф#11361

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

1,5 секунди

256 мегабайтів

Легка

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Примітка

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

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

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

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

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

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