import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.util.Vector;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class winter_festival_lewin {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        WinterFestival solver = new WinterFestival();
        solver.solve(1, in, out);
        out.close();
    }

    static class WinterFestival {
        public static final int INF = 1 << 29;
        int n;
        int m;
        List<Integer>[] graph;
        Biconnectivity bc;
        List<Integer>[] btree;
        HashMap<Integer, List<Integer>>[] mp;
        boolean[][] compat;
        boolean[] vis;
        HashMap<WinterFestival.State3, Integer> mp3;
        HashMap<WinterFestival.State1, Integer> mp1;
        HashMap<WinterFestival.State2, Integer> mp2;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            compat = new boolean[3][3];
            for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) compat[i][j] = (i + j) % 3 != 1;
            n = in.nextInt();
            m = in.nextInt();
            graph = LUtils.genArrayList(n);
            for (int i = 0; i < m; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                graph[a].add(b);
                graph[b].add(a);
            }
            bc = new Biconnectivity(graph);
            btree = bc.bcTree();
            mp = new HashMap[n];

            int maxe = 0;
            for (int i = 0; i < bc.biconnectedComponents.size(); i++) {
                int nnodes = bc.biconnectedComponents.get(i).size();
                if (nnodes <= 2) maxe += nnodes - 1;
                else maxe += nnodes;
            }
            if (maxe < m) {
                out.println(-1);
                return;
            }
            vis = new boolean[n];
            int res = 0;
            mp1 = new HashMap<>();
            mp2 = new HashMap<>();
            mp3 = new HashMap<>();
            for (int root = 0; root < n; root++) {
                if (vis[root] || bc.isCut[root]) continue;
                vis[root] = true;
                int comp = bc.bcomp[root];
                List<Integer> c = bc.biconnectedComponents.get(comp);
                int add = INF;
                if (c.size() == 2) {
                    for (int i = 0; i < 3; i++) {
                        add = Math.min(add, dfs_edge(comp, root, i));
                    }
                } else {
                    for (int i = 0; i < 3; i++) {
                        for (int j = 0; j < 3; j++) {
                            if (!compat[i][j]) continue;
                            add = Math.min(add, dfs_cyc(comp, root, i, j));
                        }
                    }
                }
                if (add >= INF) {
                    out.println(-1);
                    return;
                }
                res += add;
            }
            out.println(res);
        }

        int dfs_edge(int comp, int node, int val) {
            vis[node] = true;
            List<Integer> c = bc.biconnectedComponents.get(comp);
            int res = INF;
            int other = c.get(0) == node ? c.get(1) : c.get(0);
            vis[other] = true;
            if (val == 2) {
                res = Math.min(res, 2 + (bc.isCut[other] ? dfs_cut(other, comp, 0, true) : 0));
                res = Math.min(res, 2 + (bc.isCut[other] ? dfs_cut(other, comp, 1, true) : 0));
            } else {
                res = Math.min(res, val + (bc.isCut[other] ? dfs_cut(other, comp, val, false) : 0));
            }
            return res;
        }

        int dfs_cyc(int comp, int node, int first, int last) {
            vis[node] = true;
            List<Integer> c = bc.biconnectedComponents.get(comp);
            WinterFestival.State3 s = new WinterFestival.State3(comp, node);
            Integer idx = mp3.get(s);
            if (idx == null) mp3.put(s, idx = c.indexOf(node));

            return dfs_cyc_inner(comp, idx, idx + 1, last, first, first & 1, c);
        }

        int dfs_cyc_inner(int comp, int node, int id, int last, int cedge, int parity, List<Integer> c) {
            WinterFestival.State1 s = new WinterFestival.State1(comp, id, last, cedge, parity);
            Integer t = mp1.get(s);
            if (t != null) return t;

            if (id == node + c.size())
                return parity == 1 && cedge == last ? cedge : INF;
            int cur = c.get(id % c.size());
            vis[cur] = true;

            int res = INF;
            if (bc.isCut[cur]) {
                for (int nxt = 0; nxt < 3; nxt++) {
                    if (!compat[nxt][cedge]) continue;
                    int fpar = (nxt == 2) ? cedge : nxt;
                    boolean h2 = (nxt == 2) || (cedge == 2);
                    res = Math.min(res,
                            dfs_cut(cur, comp, fpar, h2) +
                                    dfs_cyc_inner(comp, node, id + 1, last, nxt, parity ^ (nxt & 1), c) +
                                    cedge
                    );
                }
            } else {
                for (int nxt = 0; nxt < 3; nxt++) {
                    if (!compat[nxt][cedge]) continue;
                    res = Math.min(res, dfs_cyc_inner(comp, node, id + 1, last, nxt, parity ^ (nxt & 1), c) + cedge);
                }
            }
            mp1.put(s, res);
            return res;
        }

        int dfs_cut(int cut, int parcomp, int frompar, boolean has2) {
            return dfs_cut_inner(cut, parcomp, frompar, has2, 0);
        }

        int dfs_cut_inner(int cut, int parcomp, int frompar, boolean has2, int id) {
            vis[cut] = true;
            WinterFestival.State2 s = new WinterFestival.State2(cut, frompar, id, has2);
            Integer t = mp2.get(s);
            if (t != null) return t;

            if (id == btree[bc.bcomp[cut]].size()) return 0;
            int nxt = btree[bc.bcomp[cut]].get(id);
            if (nxt == parcomp) return dfs_cut_inner(cut, parcomp, frompar, has2, id + 1);
            int res = INF;
            List<Integer> c = bc.biconnectedComponents.get(nxt);
            if (c.size() == 2) {
                for (int i = 0; i < 3; i++) {
                    if (!compat[frompar][i]) continue;
                    if (has2 && i == 2) continue;
                    boolean nhas2 = has2 || (i == 2);
                    res = Math.min(res, dfs_edge(nxt, cut, i) + dfs_cut_inner(cut, parcomp, frompar, nhas2, id + 1));
                }
            } else {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (!compat[i][j] || !compat[i][frompar] || !compat[j][frompar]) continue;
                        if (has2 && (i == 2 || j == 2)) continue;
                        boolean nhas2 = has2 || (i == 2) || (j == 2);
                        res = Math.min(res, dfs_cyc(nxt, cut, i, j) + dfs_cut_inner(cut, parcomp, frompar, nhas2, id + 1));
                    }
                }
            }
            mp2.put(s, res);
            return res;
        }

        static class State3 {
            int comp;
            int node;

            public State3(int comp, int node) {
                this.comp = comp;
                this.node = node;
            }


            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;

                WinterFestival.State3 state3 = (WinterFestival.State3) o;

                if (comp != state3.comp) return false;
                return node == state3.node;
            }


            public int hashCode() {
                int result = comp;
                result = 31 * result + node;
                return result;
            }

        }

        static class State1 {
            int comp;
            int id;
            int last;
            int cedge;
            int parity;

            State1(int comp, int id, int last, int cedge, int parity) {
                this.comp = comp;
                this.id = id;
                this.last = last;
                this.cedge = cedge;
                this.parity = parity;
            }


            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;

                WinterFestival.State1 state = (WinterFestival.State1) o;

                if (comp != state.comp) return false;
                if (id != state.id) return false;
                if (last != state.last) return false;
                if (cedge != state.cedge) return false;
                return parity == state.parity;
            }


            public int hashCode() {
                int result = comp;
                result = 31 * result + id;
                result = 31 * result + last;
                result = 31 * result + cedge;
                result = 31 * result + parity;
                return result;
            }

        }

        static class State2 {
            int cut;
            int frompar;
            int id;
            boolean has2;

            State2(int cut, int frompar, int id, boolean has2) {
                this.cut = cut;
                this.frompar = frompar;
                this.id = id;
                this.has2 = has2;
            }


            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;

                WinterFestival.State2 state2 = (WinterFestival.State2) o;

                if (cut != state2.cut) return false;
                if (frompar != state2.frompar) return false;
                if (id != state2.id) return false;
                return has2 == state2.has2;
            }


            public int hashCode() {
                int result = cut;
                result = 31 * result + frompar;
                result = 31 * result + id;
                result = 31 * result + (has2 ? 1 : 0);
                return result;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class Biconnectivity {
        List<Integer>[] graph;
        boolean[] visited;
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        int time;
        int[] tin;
        int[] lowlink;
        int n;
        public List<String> bridges;
        public boolean[] isCut;
        public List<List<Integer>> edgeBiconnectedComponents;
        public List<List<Integer>> biconnectedComponents;
        public List<Integer> cutPoints;
        public int[] bcomp;

        public Biconnectivity(List<Integer>[] graph) {
            this.graph = graph;
            n = graph.length;
            visited = new boolean[n];
            stack1 = new Stack<>();
            stack2 = new Stack<>();
            time = 0;
            tin = new int[n];
            lowlink = new int[n];
            isCut = new boolean[n];
            edgeBiconnectedComponents = new ArrayList<>();
            biconnectedComponents = new ArrayList<>();
            cutPoints = new ArrayList<>();
            bridges = new ArrayList<>();

            for (int u = 0; u < n; u++)
                if (!visited[u])
                    dfs(u, -1);
        }

        public List<Integer>[] bcTree() {
            int nodes = cutPoints.size() + biconnectedComponents.size();
            List<Integer>[] g = LUtils.genArrayList(nodes);
            bcomp = new int[n];
            int gg = 0;
            for (int i = 0; i < n; i++) {
                if (isCut[i]) {
                    bcomp[i] = biconnectedComponents.size() + (gg++);
                }
            }
            gg = 0;
            for (List<Integer> comp : biconnectedComponents) {
                int c = gg++;
                for (int u : comp) {
                    if (!isCut[u]) bcomp[u] = c;
                    else {
                        g[c].add(bcomp[u]);
                        g[bcomp[u]].add(c);
                    }
                }
            }
            return g;
        }

        void dfs(int u, int p) {
            visited[u] = true;
            lowlink[u] = tin[u] = time++;
            stack1.add(u);
            stack2.add(u);
            int children = 0;
            boolean cutPoint = false;
            for (int v : graph[u]) {
                if (v == p)
                    continue;
                if (visited[v]) {
                    lowlink[u] = Math.min(lowlink[u], tin[v]); // or lowlink[u] = Math.min(lowlink[u], lowlink[v]);
                } else {
                    dfs(v, u);
                    lowlink[u] = Math.min(lowlink[u], lowlink[v]);
                    cutPoint |= tin[u] <= lowlink[v];
                    if (lowlink[v] >= tin[u]) {
                        List<Integer> component = new ArrayList<>();
                        component.add(u);
                        while (component.get(component.size() - 1) != v) {
                            component.add(stack1.pop());
                        }
                        biconnectedComponents.add(component);
                    }
                    if (tin[u] < lowlink[v]) // or if (lowlink[v] == tin[v])
                        bridges.add("(" + u + "," + v + ")");
                    ++children;
                }
            }
            if (p == -1)
                cutPoint = children >= 2 || children == 0;
            if (cutPoint) {
                cutPoints.add(u);
                isCut[u] = true;
            }
            if (tin[u] == lowlink[u]) {
                List<Integer> component = new ArrayList<>();
                while (true) {
                    int x = stack2.pop();
                    component.add(x);
                    if (x == u)
                        break;
                }
                edgeBiconnectedComponents.add(component);
            }
        }

    }

    static class LUtils {
        public static <E> List<E>[] genArrayList(int size) {
            return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }
}