#include <cstdio> const int Q=100006; int n,q; int lst[Q],val[2*Q],nxt[2*Q],nr; void add(int x, int y) { val[++nr]=y; nxt[nr]=lst[x]; lst[x]=nr; } int s[Q],f[Q]; int e[2*Q],ct; int lg[2*Q]; int h[Q]; int r[17][Q]; int lca(int a, int b) { int d,g; if(s[a]<s[b]) { d=s[b]-s[a]+1; g=lg[d]; d=1<<g; if(h[r[g][s[a]]] < h[r[g][s[b]-d+1]]) return r[g][s[a]]; else return r[g][s[b]-d+1]; } else { d=s[a]-s[b]+1; g=lg[d]; d=1<<g; if(h[r[g][s[b]] ] < h[r[g][s[a]-d+1] ]) return r[g][s[b]]; else return r[g][s[a]-d+1]; } } void rmq() { for(int i=2; i<2*Q; i++) lg[i]=lg[i>>1]+1; for(int i=1; i<=ct; i++) r[0][i]=e[i]; int to,to2; for(int k=1; k<=16; k++) { to=1<<k; to2=1<<(k-1); for(int i=1; i<=ct-to+1; i++) { if(h[ r[k-1][i] ] < h[ r[k-1][i+to2] ]) r[k][i]=r[k-1][i]; else r[k][i]=r[k-1][i+to2]; } } } void euler(int nod) { e[++ct]=nod; s[nod]=ct; int p=lst[nod]; while(p) { if(s[val[p]]==0) { h[val[p]]=h[nod]+1; euler(val[p]); e[++ct]=nod; } p=nxt[p]; } f[nod]=ct; } int main() { // freopen("bosses.in","r",stdin); // freopen("bosses.out","w",stdout); scanf("%d%d",&n,&q); int a,b; for(int i=1; i<n; i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } h[1]=1; euler(1); rmq(); int rad=1; int t; int l1,l2,lr; for(int i=1; i<=q; i++) { scanf("%d",&t); if(t==1) { scanf("%d",&rad); } else { scanf("%d%d",&a,&b); l1=lca(rad,a); l2=lca(rad,b); lr=lca(a,b); int min=l1; if(h[l2]>h[min]) min=l2; if(h[lr]>h[min]) min=lr; if(min==a || min==b) { printf("-1\n"); } else printf("%d\n",min); /* continue; if(lr==a) { if(h[l2]<=h[a] || l2==b) { printf("-1\n"); } else printf("%d\n",l2); } else if(lr==b) { if(h[l1]<=h[b] || l1==a) printf("-1\n"); else printf("%d\n",l1); } else { if(l1==a || l2==b) printf("-1\n"); else if(h[l1]<=h[lr] && h[l2]<=h[lr]) printf("%d\n",lr); else if(h[l1]>h[l2]) printf("%d\n",l1); else printf("%d\n",l2); } */ } } return 0; }