#include <cstdio>
#include <map>
#include <vector>
using namespace std;

int Max(int x, int y) {return x > y ? x : y;}

const int MAXN = 2 * 1e5 + 5;
int c[MAXN], fa[MAXN], dep[MAXN];
map<int, int> ans[MAXN];
vector<int> num[MAXN];
bool flag[MAXN];

void Make_Set(int n) {
	for(int i = 1; i <= n; i++) {
		fa[i] = i;	
		dep[i] = 0;
		ans[i][c[i]] = 1;	
		num[i].push_back(c[i]);
	}
}

int Find_Set(int x) {
	if(fa[x] != x)
		return fa[x] = Find_Set(fa[x]);
	return x;
}

int main() {
	int n, q, ma = 0;
	scanf ("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) 
		scanf ("%d", &c[i]);
	Make_Set(n);
	for(int i = 1; i <= q; i++) {
		int opt, x, y;
		scanf ("%d %d %d", &opt, &x, &y);
		if(opt == 1) {
			int u = Find_Set(x), v = Find_Set(y);
			if(u != v) {
				if(dep[u] > dep[v]) {
					for(int j = 0; j < num[v].size(); j++) {
						bool flag = false;
						if(ans[u][num[v][j]] == 0)
							flag = true;
						ans[u][num[v][j]] += ans[v][num[v][j]];		
						if(ans[u][num[v][j]] > 0 && flag)
							num[u].push_back(num[v][j]);
					}
					fa[v] = u;
				}
				else if(dep[u] < dep[v]) {
					for(int j = 0; j < num[u].size(); j++) {
						bool flag = false;
						if(ans[v][num[u][j]] == 0)
							flag = true;
						ans[v][num[u][j]] += ans[u][num[u][j]];		
						if(ans[v][num[u][j]] > 0 && flag)
							num[v].push_back(num[u][j]);
					}						
					fa[u] = v;
				}
				else {
					for(int j = 0; j < num[v].size(); j++) {
						bool flag = false;
						if(ans[u][num[v][j]] == 0)
							flag = true;
						ans[u][num[v][j]] += ans[v][num[v][j]];		
						if(ans[u][num[v][j]] > 0 && flag)
							num[u].push_back(num[v][j]);
					}		
			        fa[v] = u;
			        if(dep[u] == dep[v]) 
						dep[u]++;
				}
			}
		}
		else 
			printf("%d\n", ans[Find_Set(x)][y]);
	}
	return 0;
}
//dp d[i][j]表示是i到j的最短回文串长度
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define pii pair<int,int> 
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn=1005;
vector<int> g[maxn][26];
int d[maxn][maxn];
int n,m;
void solve()
{
	memset(d,-1,sizeof(d));
	cin>>n>>m;
	queue<pii> q;
	rep(i,1,n+1){
		d[i][i]=0;
		q.emplace(i,i);
	}
	while(m--){
		int x,y,z;
		char ch;
		cin>>x>>y>>ch;
		z=ch-'a';
		g[x][z].emplace_back(y);
		g[y][z].emplace_back(x);
		if(x!=y){
			d[x][y]=d[y][x]=1;
			q.emplace(x,y);
		}
	}
	while(!q.empty()){
		auto [u,v]=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(!g[u][i].empty()&&!g[v][i].empty()){
				int len1=g[u][i].size(),len2=g[v][i].size();
				for(int j=0;j<len1;j++){
					for(int k=0;k<len2;k++){
						int u1=g[u][i][j],v1=g[v][i][k];
						if(d[u1][v1]==-1){
							d[u1][v1]=d[v1][u1]=d[u][v]+2;
							q.emplace(u1,v1);
						}
					}
				}
			}
		}
	}
	cout<<d[1][n]<<endl;
}
int main()
{
    solve();
    return 0;
}
