#include <bits/stdc++.h>
using namespace std;
inline constexpr void chkmin(int& x,const int& y){ if(y<x) x=y; }
const int N=2e5+10;
const int trs[3][7]={{0,2,2,0,5,5,0},{0,3,0,3,6,0,6},{0,4,5,6,0,0,0}};
int n,m;
vector<int> g[N];
int dfn[N],low[N],dfcnt;
vector<int> g2[N]; int nc;
int stk[N],top;
void tarjan(int u,int fa){
	dfn[u]=low[u]=++dfcnt;
	stk[++top]=u;
	for(int v:g[u]) if(v!=fa){
		if(!dfn[v]){
			tarjan(v,u);
			if(low[v]==-1) {
				low[u]=-1;
				return;
			}
			if(low[v]<dfn[u]){
				if(low[u]!=dfn[u]){
					low[u]=-1;
					return;
				}else{
					low[u]=low[v];
				}
			}
			if(low[v]==dfn[u]){
				// make ring
				int ring=++nc;
				g2[ring].clear();
				g2[u].push_back(ring);
				while(stk[top]!=v){
					int w=stk[top--];
					g2[ring].push_back(w);
				}
				top--;
				g2[ring].push_back(v);
			}else if(low[v]>dfn[u]){
				// make tree edge
				g2[u].push_back(v);
				while(stk[top]!=v) top--; top--;
			}
		}else if(dfn[v]<dfn[u]){
			if(low[u]!=dfn[u]){
				low[u]=-1;
				return;
			}else{
				low[u]=dfn[v];
			}
		}
	}
}
struct DP{
	int a[7];
	DP(){ memset(a,0x3f,sizeof(a)); }
	inline constexpr int& operator[](const int &x){ return a[x]; }
	inline constexpr const int& operator[](const int &x) const { return a[x]; }
	inline void clear(){ memset(a,0x3f,sizeof(a)); }
	inline friend DP operator+(DP ls,const DP& rs){ for(int i=1;i<=6;i++) chkmin(ls[i],rs[i]); return ls; }
	void print(){ for(int i=1;i<=6;i++) if(a[i]>1e9) printf("x "); else printf("%d ",a[i]); }
};
DP merge(const DP& u,const DP& v,int w){
	auto T=trs[w];
	DP nu;
	for(int s=1;s<=6;s++) {
		int ns=T[s];
		if(ns) for(int t=1;t<=6;t++) if(T[t]) chkmin(nu[ns],u[s]+v[t]+w);
	}
	return nu;
}
DP trans(const DP& u,int w){
	auto T=trs[w];
	DP nu;
	for(int i=1;i<=6;i++) if(T[i]) {
		chkmin(nu[T[i]],u[i]+w);
	}
	return nu;
}
DP dtrans(const DP& u,int w){
	auto T=trs[w];
	DP nu;
	for(int i=1;i<=6;i++) if(T[i]) {
		chkmin(nu[T[i]],u[i]);
	}
	return nu;
}
DP f[N];
void dfs(int u,int fa){
//	printf("dfs %d %d\n",u,fa);
	f[u][1]=0;
	for(int v:g2[u]) if(v!=fa){
		if(v<=n){
			dfs(v,u);
			f[u]=merge(f[u],f[v],0)+merge(f[u],f[v],1)+merge(f[u],f[v],2);
		}else{
//			printf("ring %d\n",v);
			vector<int>& V=g2[v];
			for(int w:V) dfs(w,v);
			DP _[2][3][2];
			auto F=_[0],G=_[1];
			F[0][0]=trans(f[V[0]],0);
			F[1][1]=trans(f[V[0]],1);
			F[2][0]=trans(f[V[0]],2);
//			for(int s:{0,1,2}) for(int c:{0,1}) {
//				printf("F[%d][%d]: ",s,c);
//				F[s][c].print(); puts("");
//			}
//			puts("");
			for(int i=1;i<V.size();i++){
				swap(F,G);
				memset(F,0x3f,sizeof(_[0]));
				for(int s:{0,1,2}) for(int c:{0,1}) for(int w:{0,1,2}){
					F[s][c^(w&1)]=F[s][c^(w&1)]+merge(f[V[i]],G[s][c],w);
				}
//				for(int s:{0,1,2}) for(int c:{0,1}) {
//					printf("F[%d][%d]: ",s,c);
//					F[s][c].print(); puts("");
//				}
//				puts("");
//				printf("F[0]: "); F[0].print(); puts("");
//				printf("F[1]: "); F[1].print(); puts("");
			}
			f[u]=
			merge(dtrans(f[u],0),F[0][1],0)+
			merge(dtrans(f[u],1),F[1][1],0)+
			merge(dtrans(f[u],2),F[2][1],0)+
			merge(dtrans(f[u],0),F[0][0],1)+
			merge(dtrans(f[u],1),F[1][0],1)+
			merge(dtrans(f[u],2),F[2][0],1)+
			merge(dtrans(f[u],0),F[0][1],2)+
			merge(dtrans(f[u],1),F[1][1],2)+
			merge(dtrans(f[u],2),F[2][1],2);
		}
	}
//	printf("f[%d]: ",u); f[u].print(); puts("");
}
void solve(){
	cin>>n>>m;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++){
		g[i].clear(); g2[i].clear();
		f[i].clear(); dfn[i]=0;
	}
	nc=n;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int ans=0;
	for(int i=1;i<=n;i++) if(!dfn[i]) {
		top=0;
		tarjan(i,i);
		if(low[i]==-1){
			cout<<"-1\n";
//			cout<<("fhediwsahfewq\n");
			return;
		}
		dfs(i,i);
		int cur=min({f[i][6],f[i][1],f[i][2],f[i][3],f[i][4],f[i][5]});
		if(cur>=1e9) {
			cout<<"-1\n";
			return;
		}
		ans+=cur;
	}
	cout<<ans<<endl;
}
int main(){
//	ios::sync_with_stdio(false);
//	#ifndef LCH
//		freopen("tempest.in","r",stdin);
//		freopen("tempest.out","w",stdout);
//	#endif
//	int tc; cin>>tc;
//	while(tc--) {
//		solve();
////		cout<<"================"<<endl;
//	}
	solve();
}