process.stdin.resume();
process.stdin.setEncoding('utf8');

var g_input = '';
process.stdin.on('data', function(chunk) {
    g_input += chunk;
});

process.stdin.on('end', function() {
    Main(g_input.split(/\r?\n/));
});

function Main(input) {

    var nmstr = input[0].split(' ');
    var n = parseInt(nmstr[0], 10);
    var m = parseInt(nmstr[1], 10);
    var nodes = new Array(n);
    for (var i = 0; i < n; i++) {
        nodes[i] = {index: i, edges: []};
    }
    for (var i = 0; i < m; i++) {
        var abstr = input[i + 1].split(' ');
        var a = parseInt(abstr[0], 10);
        var b = parseInt(abstr[1], 10);
        nodes[a - 1].edges.push(b);
        nodes[b - 1].edges.push(a);
    }


    var color = new Array(n);
    for (var i = 0; i < n; i++) {
        color[i] = -1;
    }
    color[0] = 0;

    var isBiparite = true;
    var q = [];
    q.push(nodes[0]);
    while (q.length > 0) {

        var now = q.shift();

        for (var i = 0; i < now.edges.length; i++) {
            var next = now.edges[i] - 1;
            if (color[now.index] == color[next]) {
                isBiparite = false;
                break;
            }
            else {
                if (color[next] < 0) {
                    color[next] = 1 - color[now.index];
                    q.push(nodes[next]);
                }
            }
        }
        if (!isBiparite) {
            break;
        }
    }

    var ans = 0;
    if (isBiparite) {
        var sum = 0;
        for (var i = 0; i < n; i++) {
            sum += color[i];
        }
        ans = sum * (n - sum) - m;
    }
    else {
        ans = n * (n - 1) / 2 - m;
    }

    console.log(ans);

    return 0;
}
