#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip> 
#include <stdio.h>
//eolibraries
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define sz(c) (ll)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define pii pair <ll,ll>
#define rep(i,n) for(ll i = 0 ; i < n ; i++) 
#define drep(i,n) for(ll i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(ll i = x ; i < n ; i++)
#define vi vector <ll> 
#define vec(...) vector<__VA_ARGS__>
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//eodefine
using namespace std;

const ll max_n = 903002;
struct dsuni {
    ll n;
    vector<ll> par, siz , color;

    dsuni(ll m) {
		init(m);
    }
    
    void init(ll m) {
    	n=m;
		par.resize(n,0); siz.resize(n,0); color.resize(n,0);
		rep(i,n) {
			par[i] = i; siz[i] = 1;
		}
    }

 	ll parent(ll x) {
	  return par[x] == x ? x : parent(par[x]);
	}
    
    ll getsize(ll x) {
    	return siz[parent(x)];
    }

    void mkuni(ll x , ll y , ll type = 0) {
		ll a = parent(x) , b = parent(y);
		if(a == b) return;
		if(siz[a] > siz[b]) {
		// rm(b);
			siz[a] += siz[b];
			par[b] = a;
			return;
		}
		// rm(a);
		siz[b] += siz[a];
		par[a] = b;
	}

 	bool isuni(ll x, ll y) {
		ll a = parent(x) , b = parent(y);
		return a == b;
	}
};
ll a[max_n];
int main(){
fcin;
	ll n;
	cin>>n;

	rep(i,n){
		cin>>a[i];
	}

	dsuni dsu(max_n);

	rep(i,n){
		dsu.mkuni(a[i],a[n-i-1]);
	}
	
	ll ans=0;

	rep(i,max_n){
		if(i==dsu.parent(i)){
			ans += max((ll)0,dsu.siz[i]-1);
		}
	}

	cout<<ans<<"\n";
/*
*/
    return 0;   
}
//#define _DEBUG
#pragma GCC optimize("O2")
#include "bits/stdc++.h"
//#include <atcoder/all>
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,a5,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#define debug_6(x1,x2,x3,x4,x5,x6) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<", "#x6<<": "<<x6<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_6,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define prind(argument) cout<<std::fixed<<setprecision(13)<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define puba(a) emplace_back(a)
#define pubamp(a,b) emplace_back(mp(a,b))
typedef long long ll;
typedef long double ld;
using namespace std;
//using namespace atcoder;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
vint adj[1001][26];
bool connect[1001][1001]={};
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int N,M;
	int A[1001],B[1001];
	char C[1001];
	bool alre[1001][1001]={};
	scan(N>>M);
	rep(i,M){
		scan(A[i]>>B[i]>>C[i]);
		A[i]--; B[i]--;
		adj[A[i]][C[i]-'a'].puba(B[i]);
		adj[B[i]][C[i]-'a'].puba(A[i]);
		connect[A[i]][B[i]]=1;
		connect[B[i]][A[i]]=1;
	}
	if(connect[0][N-1]){
		prin(1);
		return 0;
	}
	vpint record;
	record.pubamp(0,N-1);
	alre[0][N-1]=alre[N-1][0]=1;
	int ans=INF;
	bool owari=0;
	for(int cnt=1;!record.empty();cnt++){
		vpint before=record;
		record.clear();
		for(const auto& pp:before){
			int u1=pp.first,u2=pp.second;
			debug(cnt,u1+1,u2+1);
			rep(k,26){
				for(const auto& v1:adj[u1][k]){
					for(const auto& v2:adj[u2][k]){
						if(alre[v1][v2]==0){
							alre[v1][v2]=1;
							alre[v2][v1]=1;
							if(v1==v2){
								chmin(ans,cnt*2);
								owari=1;
							}
							else if(connect[v1][v2]){
								chmin(ans,cnt*2+1);
								owari=1;
							}
							else record.pubamp(v1,v2);
						}
					}
				}
			}
		}
		if(owari){
			prin(ans);
			return 0;
		}
	}
	prin(-1);
	return 0;
}
