// iostream is too mainstream #include <cstdio> // bitch please #include <iostream> #include <algorithm> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <cmath> #include <iomanip> #include <time.h> #define dibs reserve #define OVER9000 1034567890 #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++) #define tisic 47 #define soclose 1e-9 #define chocolate win // so much chocolate #define patkan 9 #define ff first #define ss second #define abs(x) ((x < 0)?-(x):x) #define uint unsigned int #define dbl long double using namespace std; // mylittledoge int main() { cin.sync_with_stdio(0); cin.tie(0); int N,M; cin >> N >> M; vector< vector<int> > G(N+M); vector<int> ch(N+M); string s; cin >> s; for(int i =0; i < N; i++) ch[i] =s[i]-'a'; for(int i =1; i < N; i++) { int a,b; cin >> a >> b; G[--a].push_back(--b); G[b].push_back(a);} vector< pair<int,int> > quer(1000000); int Q =0; for(int i =0; i < M; i++) { int t; cin >> t; if(t == 2) { int x; cin >> x >> s; ch[N] =s[0]-'a'; G[N].push_back(--x); G[x].push_back(N); N++; continue;} cin >> quer[Q].ff >> quer[Q].ss; Q++;} vector< vector<int> > par(20,vector<int>(N,-1)); vector<int> dep(N,0); queue<int> q; q.push(0); par[0][0] =0; vector< vector<int> > sum(26,vector<int>(N,0)); while(!q.empty()) { sum[ch[q.front()]][q.front()]++; ALL_THE(G[q.front()],it) if(par[0][*it] == -1) { par[0][*it] =q.front(); dep[*it] =1+dep[q.front()]; for(int i =0; i < 26; i++) sum[i][*it] =sum[i][q.front()]; q.push(*it);} q.pop();} for(int i =1; i < 20; i++) for(int j =0; j < N; j++) par[i][j] =par[i-1][par[i-1][j]]; for(int i =0; i < Q; i++) { int u =quer[i].ff-1, v =quer[i].ss-1; if(dep[u] > dep[v]) swap(u,v); int a =u, b =v; for(int k =19; k >= 0; k--) if(dep[par[k][b]] >= dep[a]) b =par[k][b]; for(int k =19; k >= 0; k--) if(par[k][b] != par[k][a]) { b =par[k][b]; a =par[k][a];} if(a != b) a =par[0][a]; int ans =0; for(int j =0; j < 26; j++) { if(a == 0) {if((sum[j][u]+sum[j][v]-sum[j][a])%2 != 0) ans++;} else {if((sum[j][u]+sum[j][v]-sum[j][a]-sum[j][par[0][a]])%2 != 0) ans++;} } cout << ans << "\n";} return 0;} // look at my code // my code is amazing