#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T> void verr(const set<T> &st) { repa(a, st) cerr << a << " "; cerr << endl; }
template <class S, class T> void verr(const map<S, T> &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; }
template <class S, class T, class N> void verr(const vector<pair<S,T>>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; }
template <class T, class N> void verr(const vector<T>& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    ll N, M;
    cin >> N >> M;
    vvc<ll> adj(N, vl(N));

    vc<vvc<ll>> G(N, vvc<ll>(26));
    rep(i, M){
        ll a, b;
        char c;
        cin >> a >> b >> c, a--, b--;
        ll ci = c - 'a';
        G[a][ci].eb(b);
        G[b][ci].eb(a);
        adj[a][b] = adj[b][a] = true;
    }


    map<pair<ll, ll>, ll> mp;
    mp[{0, N - 1}] = 0;

    queue<pair<ll, ll>> q;
    q.emplace(0, N - 1);

    ll ans = INF;
    while(!q.empty()){
        auto [s, t] = q.front();
        ll cost = mp[{s, t}];
        q.pop();

        if(adj[s][t]){
            cout << cost + 1 << endl;
            return 0;
        }

        rep(c, 26){
            repa(tos, G[s][c]){
                repa(tot, G[t][c]){
                    if (mp.count({tos, tot})) continue;
                    mp[{tos, tot}] = cost + 2;
                    if(tos == tot){
                        cout << mp[{tos, tot}] << endl;
                        return 0;
                    }else{
                        q.emplace(tos, tot);
                    }
                }
            }
        }
    }

    cout << -1 << endl;
}
#include <bits/stdc++.h>
using namespace std;
int a[200100], pos[200100];
int main(){
    int i, j, N, ans1 = 0, ans2 = 0; cin>>N;
    for(i=1; i<=N; i++) {
        scanf("%d", &a[i]); pos[a[i]] = i;
        if(a[i] > i) ans2 += a[i] - i;
        if(a[i] == i) { cout<<-1; return 0; }
        if(a[i] < i) ans1 += i - a[i];
    }
    if(ans1 != N-1 || ans2 != N-1) { cout<<-1; return 0; }
    for(i=1; i<=N; i++) {
        if(pos[i] != i) {
            for(j=pos[i]-1; j>=i; j--){
                swap(a[j], a[j+1]);
                pos[a[j]] = j; pos[a[j+1]] = j+1;
                printf("%d\n", j);
            }
        }
    }

}
