#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define next Cry_For_theMoon
using namespace std;
const int MAXN=25,LIM=1<<19; 
int n,m,g[MAXN][MAXN];
int f[LIM],d[LIM],ans,vis[MAXN];
inline int Min(int a,int b){
	return (a<b)?a:b; 
}
int main(){
	scanf("%d%d",&n,&m);
	ans=n;
	for(int i=1;i<=n;i++){
		g[i][i]=1;
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		g[u][v]=g[v][u]=1;
	}
	for(int i=0;i<n;i++){
		f[1<<i]=1;
	}
	for(int i=1;i<(1<<n);i++){
		if(f[i])continue;
		memset(vis,0,sizeof vis);
		f[i]=1;
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				vis[j+1]=1;	
			}
		}	
		for(int j=1;j<=n;j++){
			if(!vis[j])continue;
			for(int k=j+1;k<=n;k++){
				if(!vis[k])continue;
				if(!g[j][k]){
					f[i]=0;
					break;
				}
			} 
			if(!f[i])break;
		}
	}
	for(int i=1;i<(1<<n);i++){
		d[i]=1000;
		for(int j=i;j;j=(j-1)&i){
			if(!f[j])continue;
			d[i]=Min(d[i],1+d[j xor i]);
		}
	}
	printf("%d",d[(1<<n)-1]);
	return 0; 
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std; 
 
typedef long long ll;
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef tuple<int,int,int> ti;
typedef tuple<ll,ll,ll> tl;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<ti> vti;
typedef vector<tl> vtl;
 
typedef priority_queue<int> pq;
typedef priority_queue<ti,vector<ti>,greater<ti>> pqg;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound


int main() {
ios::sync_with_stdio(0);
cin.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	vector<vpi> adj(n);
	for(int i=0; i<m; i++){
		int a,b;
		char c;
		cin>>a>>b>>c;
		a--; b--;
		adj[a].pb(mp(b,c-'a'));
		adj[b].pb(mp(a,c-'a'));
	}
	
	vector<vector<bool>> vis(n, vector<bool>(n,false));
	vis[0][n-1]=true;
	pqg q;
	q.push(mt(0,0,n-1));
	
	while(!q.empty()){
		int a,b,s;
		tie(s,a,b)=q.top(); q.pop();
		if(a==b){
			cout<<s;
			return 0;
		}
		for(auto u:adj[a]){
			if(u.f==b){
				vis[b][b]=true;
				q.push(mt(s+1,b,b));
			}
		}
		for(auto u:adj[a]){
			for(auto v:adj[b]){
				if(vis[u.f][v.f]) continue;
				if(u.s==v.s){
					vis[u.f][v.f]=true;
					q.push(mt(s+2,u.f,v.f));
				}
			}
		}
	}
	
	cout<<-1;
	return 0;
}
