local mab = math.abs
local mfl, mce = math.floor, math.ceil
local bls, brs = bit.lshift, bit.rshift
local n, m = io.read("*n", "*n")
local t = {}
local parent = {}

for i = 1, n do
  parent[i] = 0
  t[i] = {}
  for j = 1, n do
    t[i][j] = false
  end
end

local function uf_findroot(idx)
  if parent[idx] == 0 then return 0 end
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

for i = 1, m do
  local a, b = io.read("*n", "*n")
  t[a][b], t[b][a] = true, true
end
local ngpairs = {}
-- local free_nodes = {1}
parent[1] = 0
local valid = true
for inew = 2, n do
  local nglist = {}
  for jdst = 1, inew - 1 do
    if not t[inew][jdst] then
      if parent[jdst] == 0 then
        -- infect dst item
        if parent[inew] == 0 then
          -- register new ng pair
          parent[jdst] = jdst
          parent[inew] = inew
          ngpairs[jdst] = inew
          ngpairs[inew] = jdst
        else
          local counterpart = ngpairs[uf_findroot(inew)]
          parent[jdst] = counterpart
        end
      else
        local dst_root = uf_findroot(jdst)
        local dst_counter_root = ngpairs[dst_root]
        if parent[inew] == 0 then
          parent[inew] = dst_counter_root
        else
          local inew_root = uf_findroot(inew)
          if inew_root == dst_root then
            valid = false
            break
          elseif inew_root == dst_counter_root then
            -- nothing to do
          else
            -- merge
            local inew_counter_root = ngpairs[inew_root]
            parent[inew_root] = dst_counter_root
            parent[inew_counter_root] = dst_root
            ngpairs[inew_root] = nil
            ngpairs[inew_counter_root] = nil
          end
        end
      end
    end
  end
  -- print("UNION " .. inew)
  -- for i = 1, n do
  --   print(i, uf_findroot(i))
  -- end
end
if valid then
  local used = {}
  local base = 0
  local dpval = {}
  local rootsize = {}
  for i = 1, n do
    local root = uf_findroot(i)
    if root == 0 then
      table.insert(dpval, 1)
    else
      if not rootsize[root] then rootsize[root] = 1
      else rootsize[root] = rootsize[root] + 1
      end
    end
  end
  for i = 1, n do
    local root = uf_findroot(i)
    if 0 < root then
      if not used[root] then
        local counter_root = ngpairs[root]
        used[root] = true
        used[counter_root] = true
        local c1, c2 = rootsize[root], rootsize[counter_root]
        if c2 < c1 then c1, c2 = c2, c1 end
        base = base + c1
        if c1 < c2 then
          table.insert(dpval, c2 - c1)
        end
      end
    end
  end
  -- print(base, table.concat(dpval, " "))
  -- find nearest to n / 2 by using dp
  local dp = {}
  for i = 1, n do dp[i] = false end
  if 0 < base then dp[base] = true end
  for i = 1, #dpval do
    for j = n, base + 1, -1 do
      if dp[j] then dp[j + dpval[i]] = true end
    end
    dp[base + dpval[i]] = true
  end
  local candpos = 0
  for i = 1, n do
    if dp[i]
    and mab(i * 2 - n) < mab(candpos * 2 - n) then
      candpos = i
    end
  end
  local ret = candpos * (candpos - 1)
  candpos = n - candpos
  ret = ret + candpos * (candpos - 1)
  ret = brs(ret, 1)
  print(ret)
else
  print(-1)
end


Measured memory_bytes: 6272