Вам дано простий неорієнтований граф \(G\) з \(N\) вершинами та \(M\) ребрами (простий граф не містить петель або мультиребер).

Для \(i=1,2,…,M\) \(i\)-те ребро сполучає вершину \(u_i\) ​ та вершину \(v_i\) ​. Виведіть кількість пар цілих чисел \((u,v)\), які задовольняють \(1≤u<v≤N\) і обидві наступні умови.

• Граф \(G\) не має ребра, що з’єднує вершину \(u\) і вершину \(v\).

• Додавання ребра, що з’єднує вершину \(u\) і вершину \(v\), у графі \(G\) призводить до дводольного графа.

Що таке дводольний граф?

Неорієнтований граф називається дводольним тоді і тільки тоді, коли можна пофарбувати кожну вершину в чорний або білий колір, щоб задовольнити наступну умову.

• Жодне ребро не зʼєднує вершини, пофарбовані в один колір.

Обмеження

• \(2≤N≤2×10^5\)
• \(0≤M≤min{2×10^5 ,N(N−1)/2}\)
• \(1≤u_i ​ ,v_i ​ ≤N\)
• Граф \(G\) простий.
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\).

Наступні  \(M\) рядків містять цілі числа \(u_i, v_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

5 4
4 2
3 1
5 2
3 2

Приклад вихідних даних

2

Маємо дві пари цілих чисел \((u,v)\), які задовольняють умови в постановці задачі: (1,4) і (1,5). Таким чином, ви повинні вивести 2.

Інші пари не задовольняють умови. Наприклад, для (1,3) граф \(G\) має ребро, що сполучає вершину 1 і вершину 3; для (4,5) додавання ребра, що з’єднує вершину 4 і вершину 5 у графі G, не призводить до дводольного графа.

Приклад вхідних даних

4 3
3 1
3 2
1 2

Приклад вихідних даних

0

Приклад вхідних даних

9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8

Приклад вихідних даних

9