import java.util.*



fun main(args: Array<String>?): Unit {
    val (v, e) = readLine()!!.trim().split(' ').map(String::toInt)
    val color = IntArray(v){-1}
    val nodes = Array(v){Stack<Int>()}
    repeat(e){
        val (a, b) = readLine()!!.trim().split( ' ').map(String::toInt)
        nodes[a - 1].push(b - 1)
        nodes[b - 1].push(a - 1)
    }
    val networks = ArrayList<Int>()
    for (i in 0 until v) {
        if (color[i] == -1) {
            var diff = 1
            color[i] = 0
            val stack = Stack<Int>().also { it.push(i) }
            while (stack.isNotEmpty()) {
                val top = stack.pop()
                for (next in nodes[top]) if (color[next] == -1) {
                    color[next] = (color[top] + 1) % 2
                    if (color[next] % 2 == 0) ++diff
                    else --diff
                    stack.push(next)
                }else if (color[next] == color[top]) {
                    println(-1)
                    return
                }
            }
            networks.add(Math.abs(diff))
        }
    }
    val sum = networks.sum()
    val canMake = BooleanArray(sum / 2 + 1){false}.also{it[0] = true}
    for (s in networks) {
        for (i in canMake.lastIndex - s downTo 0) if (canMake[i]) {
            canMake[i + s] = true
        }
    }
    val minDiff = canMake.lastIndex - canMake.lastIndexOf(true)
    val side = v.toLong() / 2 - minDiff
    println(side * (v - side) - e)
}
