#include <cstdio> const int Q=200007; int n,q; char v[Q]; int str[Q][20]; bool viz[Q]; int lst[Q],val[2*Q],nxt[2*Q],nr; int nrc[Q][26]; int a[26]; int h[Q]; int nrnod; int lca(int a, int b) { int aux; if(h[a]>h[b]) { aux=a; a=b; b=aux; } // b mai jos de a int d=h[b]-h[a]; int p=0; while(d) { if(d&1) b=str[b][p]; p++; d/=2; } if(a==b) return a; for(int k=18; k>=0; k--) { if(str[a][k]!=str[b][k]) { a=str[a][k]; b=str[b][k]; } } return str[a][0]; } void add(int a, int b) { val[++nr]=b; nxt[nr]=lst[a]; lst[a]=nr; } void adauga(int who, int tat, char f) { for(int i=0; i<26; i++) nrc[who][i]=nrc[tat][i]; nrc[who][f-'a']++; str[who][0]=tat; int act=tat; for(int k=1; (1<<k)<=n ; k++) { str[who][k]=str[act][k-1]; act=str[who][k]; } h[who]=h[tat]+1; } void dfs(int nod) { int act=str[nod][0]; a[v[nod]-'a']++; h[nod]=h[act]+1; for(int i=0; i<26; i++) { nrc[nod][i]=a[i]; } for(int k=1; (1<<k)<=n ; k++) { str[nod][k]=str[act][k-1]; act=str[nod][k]; } int p=lst[nod]; while(p) { if(viz[val[p]]==0) { viz[val[p]]=1; str[val[p]][0]=nod; dfs(val[p]); } p=nxt[p]; } a[v[nod]-'a']--; } int main() { // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); scanf("%d%d\n",&n,&q); gets(v+1); int a,b; for(int i=1; i<n; i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } viz[1]=1; dfs(1); int op; int x,y; char c; int l; int rez; for(int i=1; i<=q; i++) { scanf("%d",&op); if(op==2) { scanf("%d %c\n",&x,&c); adauga(++n,x,c); } else { scanf("%d %d\n",&x,&y); l=lca(x,y); rez=0; if(l==x) { for(int i=0; i<26; i++) { if((nrc[y][i]-nrc[str[l][0]][i])&1) rez++; } } else if(l==y) { for(int i=0; i<26; i++) { if((nrc[x][i]-nrc[str[l][0]][i])&1) rez++; } } else { for(int i=0; i<26; i++) { if((nrc[x][i]+nrc[y][i]-nrc[l][i]-nrc[str[l][0]][i])&1) rez++; } } printf("%d\n",rez); } } return 0; }