#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os << "[ "; 
  for(auto v:V)os << v << " "; return os << "]";
}
template<class T> ostream& operator<<(ostream &os, set<T> S){ os << "{ "; 
  for(auto s:S) os<<s<<" ";  return os<<"}"; 
}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
  return os<<"("<<P.first<<","<< P.second << ")";
}
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
  os<<"{ ";for(auto m:M)os<<"("<<m.first<<":"<<m.second<<")";
  return os<<"}";
}
#define cerr cout
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
//For multiset use less_equal operator but it does support erase operations for multiset
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define all(v) (v).begin(),(v).end()
#define For(i,n) for(int i=0;i<(int)n;++i)
#define Rev(i,n) for(int i=(int)n-1;i>=0;--i)
#define Rep(i,n) for(int i=1;i<=(int)n;++i)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mp make_pair
// inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 
const int N = 2e5 + 100;

int P[N];
int idx[N];

int A[N];
int rev[N];

int main(){
  fio; cout<<fixed<<setprecision(25);	
  int n; cin >> n;
  int x;
  for(int i = 1;i <= n ; ++i){
    cin >> x;
    A[i] = x;
    rev[A[i]] = i;
  }
  int lft = n-1;
  vi opr;
  for(int i = 1;i <= n ; ++i){
    if(A[i] == i)
      continue;
    int idx = rev[i];
    assert(idx > i);
    while(idx != i){
      opr.pb(idx-1);
      swap(A[idx],A[idx-1]);
      rev[A[idx]] = idx;
      rev[A[idx-1]] = idx-1;
      idx--;
    }
    if(opr.size() >= n)
      break;
  }
  if(opr.size() == n-1){
    for(auto it : opr)
      cout << it << endl;
    //cout << endl;
  }
  else
    cout << -1 << endl;
}














// #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define fi first
#define se second
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
// int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;}
typedef double lf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)!=1)exit(0); return x;}
typedef pair<ll,ll> pii; template<typename T> vector<T> &operator<<(vector<T> &a,T b){a.push_back(b); return a;} template<typename T> T sqr(T x){return x*x;} void print(ll x,bool e=0){printf("%lld%c",x," \n"[e]);}
const int N=1010; const ll mod=(0?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;}
#define int ll
char s[10];
vector<int> a[N][26];
int dis[N][N];
queue<pii> q;
void Solve(){
	int n=read(),m=read();
	repeat(i,0,m){
		int x=read()-1,y=read()-1; scanf("%s",s);
		a[x][*s-'a'].push_back(y);
		a[y][*s-'a'].push_back(x);
	}
	mst(dis,-1);
	dis[0][n-1]=0;
	q.push(pii(0,n-1));
	repeat(c,0,26)
	for(auto px:a[0][c])if(px==n-1){
		print(1,1);
		return;
	}
	ll ans=inf;
	while(!q.empty()){
		int x=q.front().fi,y=q.front().se; q.pop();
		if(x==y){
			ans=min(ans,dis[x][y]);
		}
		repeat(c,0,26){
			for(auto px:a[x][c])
			for(auto py:a[y][c]){
				if(dis[px][py]==-1){
					dis[px][py]=dis[py][px]=dis[x][y]+2;
					q.push(pii(px,py));
				}
			}
			for(auto px:a[x][c])if(px==y){
				ans=min(ans,dis[x][y]+1);
			}
		}
	}
	if(ans==inf)print(-1,1); else print(ans,1);
}
signed main(){
	// freopen("data.txt","r",stdin);
	int T=1; // T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}