/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.4.0"
+/

import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons, std.math;

// import dcomp.scanner, dcomp.graph.namori;

alias E = Tuple!(int, "to");

long calc(E[][] g, int[] co) {
    int n = g.length.to!int;
    if (co.sum) return 10L^^18;
    long[] sm = new long[n];
    void dfs(int p, int b) {
        sm[p] = co[p];
        foreach (e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p);
            sm[p] += sm[d];
        }
    }
    dfs(0, -1);
    return sm.map!"abs(a)".sum;
}

long solve(E[][] g) {
    int n = g.length.to!int;
    int[] col = new int[n];
    void dfs(int p, int b, int c) {
        col[p] = c;
        foreach (e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p, -c);
        }
    }
    dfs(0, -1, 1);
    return calc(g, col);
}


int main() {
    auto sc = new Scanner(stdin);
    int n, m;
    sc.read(n, m);
    E[][] g = new E[][n];
    foreach (i; 0..m) {
        int a, b;
        sc.read(a, b); a--; b--;
        g[a] ~= E(b);
        g[b] ~= E(a);
    }
    if (n % 2) {
        writeln(-1);
        return 0;
    }
    if (m == n-1) {
        //not namori
        auto ans = solve(g);
        if (ans == 10L^^18) ans = -1;
        writeln(ans);
        return 0;
    }
    auto nmr = namori(g);
    auto cy = nmr.cycles[0];
    
    int a = cy[0], b = cy[1];
    g[a] = g[a].remove!(e => e.to == b);
    g[b] = g[b].remove!(e => e.to == a);

    
    int[] col = new int[n];
    void dfs(int p, int b, int c) {
        col[p] = c;
        foreach (E e; g[p]) {
            int d = e.to;
            if (d == b) continue;
            dfs(d, p, -c);
        }
    }
    dfs(a, -1, 1);
    if (col.sum < 0) {
        col[] *= -1;
    }

    if (cy.length % 2 == 0) {
        if (col.sum) {
            writeln(-1);
            return 0;
        }
        long check(int md) {
            auto buf = col.dup;
            buf[a] += md;
            buf[b] -= md;
//            writeln(md, " ", buf, calc(g, buf));
            return calc(g, buf)+abs(md);
        }
        int l = -2*n, r = 2*n;
//        assert(check(l-1) >= check(l));
//        assert(check(r) <= check(r+1));
        while (r-l > 5) {
            int mdl = (l+l+r)/3;
            int mdr = (l+r+r)/3;
            if (check(mdl) > check(mdr)) {
                l = mdl;
            } else {
                r = mdr;
            }
        }
        writeln(iota(l, r+1).map!(md => check(md)).reduce!"min(a, b)");
//        assert(false);
    } else {
        int ad = col.sum/2;
        col[a] -= ad;
        col[b] -= ad;
        writeln(ad + calc(g, col));
    }

    return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/namori.d */
// module dcomp.graph.namori;

// import dcomp.graph.dfsinfo;

struct Namori {
    bool[] isCycle;
    int[][] cycles;
    int[] root;
    this(int n) {
        isCycle = new bool[n];
        root = new int[n];
    }
}

Namori namori(T)(T g) {
    import std.algorithm : find, each;
    import std.range;
    import std.conv : to;
    int n = g.length.to!int;
    auto info = dfsInfo(g);
    auto nmr = Namori(n);
    with (nmr) {
        //find self loop
        foreach (i; 0..n) {
            if (g[i].find!(e => e.to == i).empty) continue;
            isCycle[i] = true;
            cycles ~= [i];
        }
        foreach (p; info.vlis) {
            if (info.low[p] == info.ord[p]) continue;
            if (g[p].length == info.tr[p].length+1) continue;
            int[] v;
            int nw = p;
            while (info.ord[nw] != info.low[p]) {
                v ~= nw;
                nw = info.par[nw];
            }
            v ~= nw;
            v.each!(i => isCycle[i] = true);
            cycles ~= v;
        }
        bool[] used = new bool[n];
        void dfs(int p, int b, int r) {
            if (used[p]) return;
            used[p] = true;
            root[p] = r;
            foreach (e; g[p]) {
                int d = e.to;
                if (d == b) continue;
                if (isCycle[d]) continue;
                dfs(d, p, r);
            }
        }
        foreach (i; 0..n) {
            if (!isCycle[i]) continue;
            dfs(i, -1, i);
        }
    }
    return nmr;
}

Namori directedNamori(int[] g) {
    import std.algorithm : find, each;
    import std.range;
    import std.conv : to;
    int n = g.length.to!int;
    auto nmr = Namori(n);
    with (nmr) {
        int[] used = new int[n]; used[] = -1;
        foreach (i; 0..n) {
            if (used[i] != -1) continue;
            int j = i;
            while (used[j] == -1) {
                used[j] = i;
                j = g[j];
            }
            if (used[j] != i) continue;
            int k = j;
            int[] cy = [];
            while (true) {
                cy ~= k;
                isCycle[k] = true;
                if (g[k] == j) break;
                k = g[k];
            }
            cycles ~= cy;
        }
        int[] dp = new int[n]; dp[] = -1;
        int dfs(int p) {
            if (isCycle[p]) return p;
            if (dp[p] != -1) return dp[p];
            return dp[p] = dfs(g[p]);
        }
        foreach (i; 0..n) {
            root[i] = dfs(i);
        }
    }
    return nmr;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    string[] buf;
    private bool succ() {
        while (!buf.length) {
            if (f.eof) return false;
            buf = f.readln.split;
        }
        return true;
    }
    private bool readSingle(T)(ref T x) {
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                //string or char[10] etc
                x = buf.front;
                buf.popFront;
            } else {
                static if (isStaticArray!T) {
                    //static
                    assert(buf.length == T.length);
                }
                x = buf.map!(to!E).array;
                buf.length = 0;                
            }
        } else {
            x = buf.front.to!T;
            buf.popFront;            
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}

unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    fout.writeln("1 2 3");
    fout.writeln("ab cde");
    fout.writeln("1.0 1.0 2.0");
    fout.close;
    Scanner sc = new Scanner(File(fileName, "r"));
    int a;
    int[2] b;
    char[2] c;
    string d;
    double e;
    double[] f;
    sc.read(a, b, c, d, e, f);
    assert(a == 1);
    assert(equal(b[], [2, 3]));
    assert(equal(c[], "ab"));
    assert(equal(d, "cde"));
    assert(e == 1.0);
    assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/dfsinfo.d */
// module dcomp.graph.dfsinfo;

struct DFSInfo {
    int[] low, ord, par, vlis; //low, ord, parent, visitList
    int[][] tr; //dfs tree(directed)
    this(int n) {
        low = new int[n];
        ord = new int[n];
        par = new int[n];
        vlis = new int[n];
        tr = new int[][](n);
    }
}

DFSInfo dfsInfo(T)(T g) {
    import std.algorithm : min, each, filter;
    import std.conv : to;
    const int n = g.length.to!int;
    auto info = DFSInfo(n);
    with(info) {
        int co = 0;
        bool[] used = new bool[](n);
        void dfs(int p, int b) {
            used[p] = true;
            low[p] = ord[p] = co++;
            par[p] = b;

            bool rt = true;
            foreach (e; g[p]) {
                int d = e.to;
                if (rt && d == b) {
                    rt = false;
                    continue;
                }
                if (!used[d]) {
                    dfs(d, p);
                    low[p] = min(low[p], low[d]);
                } else {
                    low[p] = min(low[p], ord[d]);
                }
            }
        }
            
        foreach (i; 0..n) {
            if (used[i]) continue;
            dfs(i, -1);
        }
        par.filter!"a!=-1".each!((i, v) => tr[v] ~= i.to!int);
        ord.each!((i, v) => vlis[v] = i.to!int);
    }
    return info;
}


Measured memory_bytes: 30460