NAIPC18J_rpeng

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n)
#define PB push_back


template <typename T> inline void SetMin(T &a, T b) {if(b < a) a = b;}
template <typename T> inline void SetMax(T &a, T b) {if(b > a) a = b;}


const int MAXN = 2000000;

vector<int> e[MAXN];

int parent[MAXN];
vector<int> child[MAXN];

int cross_edge[MAXN];
int cross_n;
int e_low[MAXN];
int e_high[MAXN];

int is_intermediate[MAXN];

int DP[MAXN][3][3][2];

int n, m;
int vis[MAXN];


int ans;
const int VERYBIG = 1<<25;

int dfs_t;
int disc[MAXN];

void DFS(int u, int pa) {
  vis[u] = 1;
  parent[u] = pa;
  disc[u] = dfs_t++;
  for(auto v: e[u]) {
    if(v != pa) {
      if(!vis[v]) {
        child[u].PB(v);
        DFS(v, u);
      } else if(disc[v] < disc[u]) {
        e_low[cross_n] = u;
        e_high[cross_n] = v;
//printf("cross edge: %d--%d\n", u, v);
        int temp = u;
        while(temp != v) {
//printf("%d\n", temp);
          if(cross_edge[temp] != -1) {
            puts("-1");
            exit(0);
          }
          cross_edge[temp] = cross_n;
          if(temp != u) {
//printf("intermediate vertex = %d\n", temp);
            is_intermediate[temp] = 1;
          }
          temp = parent[temp];
        }
        cross_n++;
      }
    }
  }
}

int Incorporate(int &mask, int v) {
  int opp = (4 - v) % 3;
  if(((mask >> opp) % 2) == 1) return 0;
  mask |= (1<<v);
  return 1;
}

int bes[8], temp[8];

void Moo(int p, int pa) {
  for(auto v: child[p]) {
    Moo(v, p);
  }

  int i1 = 0;
  if(is_intermediate[p]) {
    FOR(i, child[p].size()) {
      if(cross_edge[p] == cross_edge[child[p][i]]) {
        swap(child[p][i], child[p][0]);
      }
    }
    i1 = 1;
  }
  FOR(i, 8) bes[i] = VERYBIG;
  bes[0] = 0;

  FR(i, i1, child[p].size()) {
    FOR(i, 8) temp[i] = VERYBIG;
    int v = child[p][i];
    if(cross_edge[v] == -1) {
      FOR(j1, 3) {
        FOR(mask, 8) {
          int mask1 = mask;
          if(Incorporate(mask1, j1)) {
            SetMin<int>(temp[mask1], bes[mask] + DP[v][j1][0][0]);
          }
        }
      }
    } else {
      FOR(j1, 3) FOR(j2, 3) {
        FOR(mask, 8) {
          int mask1 = mask;
          if(Incorporate(mask1, j1)) {
            if(Incorporate(mask1, j2)) {
              SetMin<int>(temp[mask1], bes[mask] + DP[v][j1][j2][1]);
            }
          }
        }
      }
    }
    FOR(i, 8) bes[i] = temp[i];
  }
  if(pa == -1) { //already at root, stop
    int blah = VERYBIG;
    FOR(mask, 8) {
      SetMin<int>(blah, bes[mask]);
    }
    if(blah > n * 3) {
//printf("%d\n", DP[5][1][2][1]); fflush(stdout);
//printf("%d\n", DP[2][2][2][1]); fflush(stdout);
//printf("UHOH @ %d\n", p);
      puts("-1");
      exit(0);
    }
    ans += blah;
  } else if(is_intermediate[p]) { //intermediate vertex
//printf("====intermediate====%d\n", p); fflush(stdout);
    int v = child[p][0];
//printf("to...%d\n", v);
    FOR(j, 3) FOR(j1, 3) {
      FOR(mask, 8) {
        int mask1 = mask;
//if(mask == 0 && j == 2 && j1 == 1) puts("HI");
        if(Incorporate(mask1, j)) {
          if(Incorporate(mask1, j1)) {
           FOR(j2, 3) FOR(j3, 2) {
/*
 * if(mask == 0 && j == 2 && j1 == 1) {
  printf("%d, %d: %d\n", j2, j3, DP[v][j1][j2][j3]);
}
*/
              SetMin<int>(DP[p][j][j2][(j3 + j) % 2],
                DP[v][j1][j2][j3] + j + bes[mask]);
            }
          }
        }
      }
    }
  } else if(cross_edge[p] == -1) { //only one parent, no cycle
    FOR(j, 3) {
      FOR(mask, 8) {
        int mask1 = mask;
        if(Incorporate(mask1, j)) {
          SetMin<int>(DP[p][j][0][0], bes[mask] + j);
        }
      }
    }
  } else { // parent + cross edge
//printf("====bottom====%d\n", p); fflush(stdout);
    FOR(j, 3) FOR(k, 3) {
      FOR(mask, 8) {
        int mask1 = mask;
        if(Incorporate(mask1, j)) {
          if(Incorporate(mask1, k)) {
//printf("%d %d\n", j, k);
            SetMin<int>(DP[p][j][k][(j + k) % 2], bes[mask] + j + k);
          }
        }
      }
    }
  }
}

void ShowDFSStates() {
  FOR(i, n) printf("node %d: parent = %d   cross = %d  intermeidate = %d\n", i, parent[i], cross_edge[i], is_intermediate[i]);
  puts("cross edges");
  FOR(i, cross_n) printf("%d %d\n", e_low[i], e_high[i]);
}

int main() {
  scanf("%d%d", &n, &m);
  FOR(i, m) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a; --b;
    e[a].PB(b);
    e[b].PB(a);
  }
  ans = 0;
  memset(vis, 0, sizeof(vis));
  FOR(i, n) {
    is_intermediate[i] = 0;
    cross_edge[i] = -1;
    FOR(j1, 3) FOR(j2, 3) FOR(j3, 2) {
      DP[i][j1][j2][j3] = VERYBIG;
    }
  }
  cross_n = 0;

  dfs_t = 0;
  ans = 0;
  FOR(i, n) {
    if(!vis[i]) {
      DFS(i, -1);
//ShowDFSStates();
      Moo(i, -1);
    }
  }
  printf("%d\n", ans);
  return 0;
}