import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import qualified Data.IntSet as IS
import qualified Data.IntMap as IM
import Debug.Trace

bsReadInts :: B.ByteString -> [Int]
bsReadInts = map (fst . fromJust . B.readInt) . B.words

type MyMap = IM.IntMap IS.IntSet

mkDisRel :: Int -> [[Int]] -> MyMap
mkDisRel n abs = foldr op init abs
  where
    initSet x = IS.delete x (IS.fromList [1..n])
    init = IM.fromList [(x,initSet x) | x <- [1..n]]
    op [a,b] =   IM.adjust (IS.delete a) b
               . IM.adjust (IS.delete b) a

mkOEList :: Int -> MyMap -> Maybe [Int]
mkOEList n disRel =
  mkOELSub n disRel (IS.fromList [1..n]) []

mkOELSub :: Int -> MyMap -> IS.IntSet -> [Int] -> Maybe [Int]
mkOELSub n disRel yet acc
  | IS.null yet = Just acc
  | otherwise = case oneComp of
      Nothing -> Nothing
      Just (comp, done) ->
        mkOELSub n disRel (IS.difference yet done) (comp:acc)
  where
    k:_ = IS.toList yet
    oneComp = mkOneComp disRel k
    
mkOneComp :: MyMap -> Int -> Maybe (Int, IS.IntSet)
mkOneComp disRel k =
  case mkOneCompSub disRel [k] IS.empty IS.empty of
    Nothing -> Nothing
    Just (this, that) -> Just (abs(IS.size(this) - IS.size(that)),
                               IS.union this that)

mkOneCompSub :: MyMap -> [Int] -> IS.IntSet -> IS.IntSet -> 
                Maybe (IS.IntSet, IS.IntSet)
-- mkOneCompSub disRek ks this that
--   | trace ("mkOneCompSub " ++ show ks ++ " " ++ show this ++ show that) False = undefined
mkOneCompSub disRel [] this that = Just (this, that)
mkOneCompSub disRel (k:ks) this that =
  if IS.member k that then Nothing
  else if IS.member k this then mkOneCompSub disRel ks this that
  else case IM.lookup k disRel of
  Nothing -> mkOneCompSub disRel ks this that
  Just ls -> case mkOneCompSub disRel (IS.toList ls) that (IS.insert k this) of
    Nothing -> Nothing
    Just (that', this') -> mkOneCompSub disRel ks this' that'

findMinimum :: [Int] -> Int
findMinimum is = IS.findMin (IS.filter (>= 0) cands)
  where
    cands = foldr op (IS.singleton 0) is
      where
        op i iset = IS.union (IS.map (+   i)  iset)
                          (IS.map (+ (-i)) iset)

solve :: Int -> Int -> [[Int]] -> Int
solve n m abs =
  case mkOEList n disRel of
    Nothing -> -1
    Just oddEvenList ->
      let diff = findMinimum oddEvenList
          x = (n + diff) `div` 2
          y = n - x
      in x*(x-1) `div` 2 + y*(y-1) `div` 2
  where
    disRel = mkDisRel n abs

main = do
  conts <- B.getContents
  let [n, m] : abs = map bsReadInts (B.lines conts)
      answer = solve n m abs
  putStrLn (show answer)
