#include<stdio.h> #include<vector> using namespace std; #define NMAX 100005 #define pb push_back int h[NMAX],st[NMAX],dr[NMAX]; char viz[NMAX]; int rmq[20][NMAX],n,m,nr; int prep[NMAX],nrb,centru; vector<int> v[NMAX]; inline void dfs(int nod) { viz[nod] = 1; st[nod] = ++nr; int i, vec, lim = v[nod].size(); for(i = 0; i < lim; i++) if(!viz[vec = v[nod][i]]) { h[vec] = h[nod] + 1; rmq[0][vec] = nod; dfs(vec); } dr[nod] = nr; } int find(int nod,int L) { if(!L) return nod; return find(rmq[prep[L]][nod], L - (1 << prep[L])); } int lca(int n1,int n2) { int i,aux; if(h[n1] >= h[n2]) { aux = n1; n1 = n2; n2 = aux; } n2 = find(n2, h[n2] - h[n1]); if(n1 == n2) return n1; for(i = nrb; i >= 0; i--) if(rmq[i][n1] != rmq[i][n2]) { n1 = rmq[i][n1]; n2 = rmq[i][n2]; } return rmq[0][n1]; } int main () { int i,j,a,b,sef1,sef2,sef3,tip,sef; // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d%d",&n,&m); for(i = 1; i < n; i++) { scanf("%d%d",&a,&b); v[a].pb(b); v[b].pb(a); } dfs(1); for(i = 2; i <= n; i++) prep[i] = prep[i / 2] + 1; nrb = prep[n]; for(j = 1; (1<<j) <= n; j++) for(i = 1; i <= n; i++) if(h[i] >= (1<<j)) rmq[j][i] = rmq[j - 1][rmq[j - 1][i]]; centru = 1; for(i = 1; i <= m; i++) { scanf("%d",&tip); if(tip == 1) scanf("%d",¢ru); else { scanf("%d%d",&a,&b); if(st[a] <= st[b] && dr[b] <= dr[a]) { sef = lca(b,centru); if(st[b] <= st[sef] && dr[sef] <= dr[b]) printf("-1\n"); else if(st[sef] <= st[a] && dr[a] <= dr[sef]) printf("-1\n"); else printf("%d\n",sef); } else if(st[b] <= st[a] && dr[a] <= dr[b]) { sef = lca(a,centru); if(st[a] <= st[sef] && dr[sef] <= dr[a]) printf("-1\n"); else if(st[sef] <= st[b] && dr[b] <= dr[sef]) printf("-1\n"); else printf("%d\n",sef); } else { sef1 = lca(a,b); sef2 = lca(a,centru); sef3 = lca(b,centru); if(st[a] <= st[centru] && dr[centru] <= dr[a]) printf("-1\n"); else if(st[b] <= st[centru] && dr[centru] <= dr[b]) printf("-1\n"); else if(st[sef1] < st[sef2] && dr[sef2] <= dr[sef1]) printf("%d\n",sef2); else if(st[sef1] < st[sef3] && dr[sef3] <= dr[sef1]) printf("%d\n",sef3); else printf("%d\n",sef1); } } } return 0; }