//LCA cu smenul de la heavypath O(N + M log N) #include <cstdio> #include <vector> using namespace std; #define maxn 200010 int l[maxn], niv[maxn], d[maxn], tl[maxn], f[maxn]; int a, b, nl, n, m, x, y, lvl[maxn]; vector<int> v[maxn]; void df(int nod) { f[nod]=1; d[nod]=1; if(v[nod].size()==1 && nod!=1) { l[nod]=++nl; return; } int fmax, it, dmax=0; for(int i=0; i<v[nod].size(); ++i) { it=v[nod][i]; if(f[it]==1) { lvl[nod]=lvl[it]+1; continue; } niv[it]=niv[nod]+1; df(it); d[nod]+=d[it]; if(d[it]>dmax) { dmax=d[it]; fmax=(it); } tl[l[it]]=nod; } l[nod]=l[fmax]; } int lca(int x, int y) { while(l[x]!=l[y]) { if(niv[tl[l[x]]]>niv[tl[l[y]]]) x=tl[l[x]]; else y=tl[l[y]]; } if(niv[x]<niv[y]) return x; return y; } int main() { // freopen("data.in", "r", stdin); scanf("%d%d", &n, &m); for(int i=2; i<=n; ++i) { scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } niv[1]=1; df(1); tl[l[1]]=0; int tip, x=1; while(m--) { scanf("%d", &tip); if(tip==1) scanf("%d", &x); else { scanf("%d%d", &a, &b); int s1 = lca(a, b), sx = lca(x, a), sy = lca(x, b); int rez = s1; if(lvl[sx]>lvl[rez]) rez=sx; if(lvl[sy]>lvl[rez]) rez=sy; if(rez==a || rez==b) printf("-1\n"); else printf("%d\n", rez); } } return 0; }