{-# OPTIONS_GHC -O2 #-}
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Array.Unboxed
import Data.Array.ST
import Data.STRef 
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Control.Monad.ST
import Data.List
import Data.Char
import qualified Data.Map.Strict as M

convert :: Int -> Int -> VU.Vector (Int,Int) -> V.Vector [Int]
convert n e graph = V.create $ do
    v <- VM.replicate n []
    forM_ [0..e-1] $ \i -> do
        let (x,y) = graph VU.! i
        VM.modify v (y-1:) (x-1)
        VM.modify v (x-1:) (y-1)
    return v

bipartite :: Int -> V.Vector [Int] -> Maybe (VU.Vector Int)
bipartite n graph = runST $ do
    vec <- VUM.replicate n (-1)
    VUM.write vec 0 0
    go [0] vec
    where go :: [Int] -> VUM.MVector s Int -> ST s (Maybe (VU.Vector Int))
          go [] vec = do
              vv <- VU.freeze vec
              return $ Just vv
          go (n:ns) vec = do
              now <- VUM.read vec n
              ls <- newSTRef ns
              flag <- newSTRef False
              forM_ (graph V.! n) $ \i -> do
                  b <- VUM.read vec i
                  when (b == -1) $ VUM.write vec i (1-now) >> modifySTRef ls (i:)
                  when (b == now) $ writeSTRef flag True
              ln <- readSTRef ls
              ff <- readSTRef flag
              if ff then return Nothing else go ln vec


main :: IO ()
main = do
    [n,m] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    graph <- convert n m <$> (VU.replicateM m $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine)
    print $ case bipartite n graph of
        Nothing -> (n*(n-1))`div`2-m
        Just vec -> let len = VU.sum vec in len*(n-len) - m