#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair
#define eb emplace_back

const int MAX_N = 2e6+10;
ll a, b, c, d;

void solve()
{
	if(a == c && b == d){
		cout<<0<<'\n';
	}else if((abs(a-c)+abs(b-d)<=3)||(a+b==c+d)||(a-b==c-d)){
		cout<<1<<'\n';
	}else if((a+b)%2==(c+d)%2){
		cout<<2<<'\n';
	}else{
		for(int dx=-3;dx<=3;++dx)for(int dy=-3;dy<=3;++dy){
			if(abs(dx)+abs(dy)>3) continue;
			int x=a+dx, y=b+dy;
			if(abs(x-c)+abs(y-d)<=3||(x+y==c+d)||(x-y==c-d)){
				cout<<2<<'\n';
				return;
			}
		}
		cout<<3<<'\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> a >> b >> c >> d;
	solve();
	return 0;
}
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){scanf("%s",x);}
void sc(char *x,char *y){scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){scanf("%s%s%s",x,y,z);}
void out(int x){printf("%d\n",x);}
void out(ll x){printf("%lld\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
void out(ll x,ll y){printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
const int N=1005;
int n,m;
vector<int>e[26][N];
bool vis[N][N],updated[N][N];
int dp[N][N];
struct node
{
    int u,v,w;
    node(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
    bool operator<(const node&o)const
    {
        return w>o.w;
    }
};
priority_queue<node>q;
int main()
{
    memset(dp,0x3f3f3f3f,sizeof(dp));
    //freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    sc(n,m);
    rep(i,1,m)
    {
        int u,v;char c;
        scanf("%d %d %c",&u,&v,&c);
        e[c-'a'][u].push_back(v);
        e[c-'a'][v].push_back(u);
        vis[u][v]=vis[v][u]=true;
    }
    dp[1][n]=0;
    q.push(node(1,n,0));
    while(!q.empty())
    {
        int u=q.top().u,v=q.top().v;q.pop();
        if(updated[u][v]) continue;
        updated[u][v]=true;
        rep(i,0,25)
        {
            for(int x:e[i][u])
                for(int y:e[i][v])
            if(dp[x][y]>dp[u][v]+2)
            {
                dp[x][y]=dp[u][v]+2;
                q.push(node(x,y,dp[x][y]));
            }
        }
    }
    int ans=998244353;
    rep(i,1,n) ans=min(ans,dp[i][i]);
    rep(i,1,n)
        rep(j,1,n)
        if(vis[i][j]) ans=min(ans,dp[i][j]+1);
    if(ans==998244353) ans=-1;
    out(ans);
}
