import java.util.*;
import java.io.*;

public class winterfestival_font
{
   public static void main(String[] args) throws Exception
   {
      PrintWriter out = new PrintWriter(System.out);
      new winterfestival_font(new FastScanner(System.in), out);
      out.close();
   }

   boolean isCycleOrEdge(ArrayList<Edge> comp)
   {
      TreeSet<Integer> nodes = new TreeSet<>();
      for (Edge e : comp)
      {
         nodes.add(e.i);
         nodes.add(e.j);
      }
      return nodes.size() >= comp.size();
   }

   // Given a mask of present colors, calculate the cost of placing node i
   int oo = 987654321;
   int[][] nodeDP;

   // Given some color we would like to make an edge and the current colors
   // incident to a node. Determine if this placement is allowed.
   boolean canPlace(int edgeColor, int nodeMask)
   {
      int nMask = (1<<edgeColor) | nodeMask;
      // Can't have 0 and 1 be incident.
      if ((nMask&3) == 3)
         return false;
      // Can't have (2) 2's.
      if (edgeColor == 2 && (4&nodeMask) > 0)
         return false;
      return true;
   }

   void updateEdge(Edge e)
   {
      // Update on a single edge
      int all = (1<<3)-1;
      int[] nxt = new int[1<<3];
      Arrays.fill(nxt, oo);
      for (int prevMask=0; prevMask<=all; prevMask++)
      {
         for (int mask=0; mask<=all; mask++)
         {
            for (int x=0; x<3; x++)
            {
               if (canPlace(x, mask) && canPlace(x, prevMask))
               {
                  int nxtMask = (1<<x) | mask;
                  int cost = x + nodeDP[mask][e.i] + nodeDP[prevMask][e.j];
                  nxt[nxtMask] = Math.min(nxt[nxtMask], cost);
               }
            }
         }
      }
      for (int mask=0; mask<=all; mask++)
         nodeDP[mask][e.i] = nxt[mask];
   }

   void updateCycle(ArrayList<Edge> cycle)
   {
      int all = (1<<3)-1;
      int[][][] cur = new int[2][3][1<<3];
      int[][][] nxt = new int[2][3][1<<3];
      for (int s=0; s<2; s++)
         for (int f=0; f<3; f++) 
            for (int mask=0; mask<=all; mask++)
               cur[s][f][mask] = oo;

      Edge e = cycle.get(0);
      for (int mask=0; mask<=all; mask++) 
      {
         for (int x=0; x<3; x++)
         {
            int s = x&1; 
            int nxtMask = (1<<x) | mask;
            if (canPlace(x, mask))
            {
               int cost = x + nodeDP[mask][e.i];
               cur[s][x][nxtMask] = Math.min(cur[s][x][nxtMask], cost);
            }
         }
      }

      for (int u=1; u<cycle.size(); u++)
      {
         for (int s=0; s<2; s++)
            for (int f=0; f<3; f++)
               for (int mask=0; mask<=all; mask++)
                  nxt[s][f][mask] = oo;
            
         e = cycle.get(u);
         for (int mask=0; mask<=all; mask++)
         {
            for (int prevMask=0; prevMask<=all; prevMask++)
            {
               for (int s=0; s<2; s++)
               {
                  for (int f=0; f<3; f++)
                  {
                     for (int x=0; x<3; x++)
                     {
                        if (canPlace(x, mask) && canPlace(x, prevMask))
                        {
                           int ns = (x + s)&1;
                           int nxtMask = (1<<x) | mask;
                           int cost = x + nodeDP[mask][e.i] + cur[s][f][prevMask];
                           nxt[ns][f][nxtMask] = Math.min(nxt[ns][f][nxtMask], cost);
                        }
                     }
                  }
               }
            }
         }

         for (int s=0; s<2; s++)
            for (int f=0; f<3; f++)
               for (int mask=0; mask<=all; mask++)
                  cur[s][f][mask] = nxt[s][f][mask];
      }

      // Take the best cur and place it.
      for (int mask=0; mask<=all; mask++)
         nodeDP[mask][e.i] = oo;
      for (int f=0; f<3; f++)
      {
         for (int mask=0; mask<=all; mask++)
         {
            if (canPlace(f, mask))
            {
               int nxtMask = (1<<f) | mask;
               int cost = cur[1][f][mask];
               nodeDP[nxtMask][e.i] = Math.min(nodeDP[nxtMask][e.i], cost);
            }
         }
      }
   }

   public winterfestival_font(FastScanner in, PrintWriter out)
   {
      int N = in.nextInt();
      int M = in.nextInt();
      Graph g = new Graph(N);
      int[][] edges = new int[M][];
      for (int u=0; u<M; u++)
      {
         edges[u] = new int[]{in.nextInt()-1, in.nextInt()-1};
         g.add(edges[u][0], edges[u][1]); 
      }

      DFSLowLink dfs = new DFSLowLink(g);
      for (ArrayList<Edge> comp : dfs.comps)
      {
         if (!isCycleOrEdge(comp))
         {
            out.println(-1);
            return;
         }
      }

      nodeDP = new int[1<<3][N];
      for (int mask=1; mask<(1<<3); mask++)
         for (int i=0; i<N; i++)
            nodeDP[mask][i] = oo;
      for (ArrayList<Edge> comp : dfs.comps)
      {
         if (comp.size() == 1)
            updateEdge(comp.get(0));
         else
            updateCycle(comp);
      }

      int res = 0;
      for (int i : dfs.sources)
      {
         int rr = oo;
         for (int mask=0; mask<(1<<3); mask++)
            rr = Math.min(rr, nodeDP[mask][i]);
         res += rr;
         res = Math.min(res, oo);
      }

      out.println(res == oo ? -1 : res);
   }
}

class DFSLowLink
{
   ArrayList<ArrayList<Edge>> comps;
   ArrayDeque<Edge> stk;
   boolean[] used;
   int[] low, pre;

   Graph g;
   int cnt;

   ArrayList<Integer> sources;

   DFSLowLink(Graph gg)
   {
      g = gg;
      cnt = 0;
      comps = new ArrayList<>();
      Arrays.fill(low=new int[g.N], -1);
      Arrays.fill(pre=new int[g.N], -1);
      used = new boolean[g.M+1];
      stk = new ArrayDeque<>();
      sources = new ArrayList<>();
      Edge dummy = new Edge(-1, -1, g.M);
      for (int i=0; i<g.N; i++)
      {
         dummy.i = dummy.j = i;
         if (pre[i] == -1)
         {
            sources.add(i);
            used[dummy.id] = false;
            dfs(dummy);
            if (stk.size() > 1)
               makeComp(dummy.id);
            stk.clear();
         }
      }
   }

   int dfs(Edge fwd)
   {
      if (!used[fwd.id])
      {
         stk.push(fwd);
         used[fwd.id] = true;
      }

      if (pre[fwd.j] != -1)
      {
         return low[fwd.i] = Math.min(low[fwd.i], pre[fwd.j]);
      }
  
      boolean hasPath = false;
      low[fwd.j] = pre[fwd.j] = cnt;
      cnt++;
      for (Edge e : g.adj[fwd.j])
      {
         if (e.id != fwd.id && dfs(e) < 0)
         {
            low[fwd.j] = Math.min(low[fwd.j], low[e.j]);
            if (fwd.id != g.M ? low[e.j] >= pre[fwd.j] : hasPath)
            {
               makeComp(e.id).add(stk.pop());
            }
            hasPath = true;
         }
      }
      return -1;
   }

   ArrayList<Edge> makeComp(int id)
   {
      ArrayList<Edge> comp = new ArrayList<>();
      while (stk.peek().id != id)
         comp.add(stk.pop());
      comps.add(comp);
      return comp;
   }
}

class Graph
{
   int N, M;
   ArrayList<Edge>[] adj;
   Graph(int NN)
   {
      adj = new ArrayList[N=NN];
      for (int i=0; i<N; i++)
         adj[i] = new ArrayList<>();
   }

   void add(int i, int j)
   {
      adj[i].add(new Edge(i, j, M));
      adj[j].add(new Edge(j, i, M));
      M++;
   }
}

class Edge
{
   int i, j, id;
   Edge(int i, int j, int id)
   {
      this.i = i;
      this.j = j;
      this.id = id;
   }
}

class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    
    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }
    
    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
    
    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }
    
    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }
    
    int nextInt()
    {
        return Integer.parseInt(next());
    }
    
    long nextLong()
    {
        return Long.parseLong(next());
    }
    
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
    
    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }
    
    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}