//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream

//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scan(A) scanf("%d", &(A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
//#define dispAll(A,n) cout << #A << " = "; rep(j, 0, (n)) {cout << setw(3) << A[j] << " ";} cout << endl

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) (i)/2
#define l(i) (i)*2
#define r(i) (i)*2+1

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

const int INF = 2e9+10;
const ll INF_LL = 1e18; //Be careful for overflow.
const int NONE = -1;
const ll MOD = 1e9+7;

const int N_MAX = 1e5+10; //num of vertex or element
const int M_MAX = 100000; //num of edge
const int DATA_MAX = 1000000010;

ll N;
ll M;

ll numOfColor[2] = {0};

const int WHITE = 0;
const int BLACK = 1;
#define theOtherColor(x) (1-(x))

int color[N_MAX];
vi adjacentList[N_MAX];


void display() {
    dout << "---\n";
    dout<<"    i = "; rep(i,1,N+1) disP(i); dout << endl;
    dout<<"color = "; rep(i,1,N+1) disP(color[i]); dout << endl;
    dout << endl;
    
    dout<<"W = " << numOfColor[WHITE] << endl;
    dout<<"B = " << numOfColor[BLACK] << endl;
    dout << endl;
    dout << "---\n";
}


bool checkBipartiteGraph(int i) { //深さ優先探索してる
#ifdef debug
    dout << "--------------------- checkBipartiteGraph( " << i << " ) \n";
    display();
#endif
    
    bool ret = true;
    
    if(color[i]==NONE) {
        color[i] = BLACK;
        numOfColor[ color[i] ]++;
    }
    
    int keyColor = color[i];
    
    for(auto v : adjacentList[i]) {
        if(color[v]==keyColor) {
#ifdef debug
            dout << "Found contradiction!! This is not a Bipartite Graph!!\n";
#endif
            return false;
        }
        else if(color[v]==NONE) {
            color[v] = theOtherColor(keyColor);
            numOfColor[ color[v] ]++;
            
            ret = checkBipartiteGraph(v);
            if(!ret) { //配下で矛盾が生じた場合には上位にもfalseを伝達してあげる
                return false;
            }
        }
        else { //vにすでに正しい色が着いている
            //no action
        }
    }
    
    return ret;
}


int main() {
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    //cin, coutの高速化  ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
    cin.tie(0); //cinとcoutの同期を切る
    ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
    
    //read input data
    din >> N >> M;
    
#ifdef debug
    disp(N);
    disp(M);
#endif
    
    
    //initialize
    rep(i,0,N+1) {
        color[i] = NONE;
    }
    
    //read input data and construct graph
    int a, b;
    rep(i,0,M) {
        din >> a >> b;
        
        adjacentList[a].push_back(b);
        adjacentList[b].push_back(a);
    }
    

    bool bipar = checkBipartiteGraph(1);
    
#ifdef debug
    disp(bipar);
    display();
    dout << "ans = ";
#endif
    
    dout << ( bipar ? numOfColor[WHITE]*numOfColor[BLACK] - M : N*(N-1)/2 - M) << endl;
    
    
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}

Measured memory_bytes: 6528