#include <iostream> #include <cstdio> #include <vector> #include <set> #include <queue> #define pii pair <int, int > #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; const int NMAX = 200005; const int Nmax = 100005; int aib[NMAX], nn, stramos[20][Nmax];; int ind, First[NMAX], Last[NMAX], niv[NMAX]; vector<int>Tree[Nmax]; inline void Update(int x,int y,int val){ for(;x <= nn;x += x & -x) aib[x] += val; for(y++;y <= nn;y += y & -y) aib[y] -= val; } inline int Query(int x){ int ret = 0; for(;x > 0; x -= x & -x) ret += aib[x]; return ret; } inline void Euler1(const int node,const int level){ First[node] = ++ind; niv[node] = level; for(vector <int>::iterator it = Tree[node].begin(); it != Tree[node].end(); ++it) if(First[*it]==0) Euler1(*it,level+1); Last[node] = ++ind; } int RMQ[Nmax][21], n, N, M,pos[Nmax], Log2[Nmax], Root = 1; vector < pii > Euler; inline void Read() { //freopen("date.in","r",stdin); //freopen("date.out","w",stdout); cin.sync_with_stdio(false); cin >>N >> M; int i, X, Y; for(i = 1;i < N; ++i) { cin >> X >> Y; Tree[X].pb(Y); Tree[Y].pb(X); } nn=2*N; } inline void _Euler(const int _node,const int f,const int height) { pos[_node] = ++n; Euler.pb(mp(_node,height)); vector<int>::iterator it; stramos[0][_node] = f; for(it = Tree[_node].begin();it!=Tree[_node].end();++it) { if(pos[*it]!=0) continue; _Euler(*it,_node,height+1); Euler.pb(mp(_node,height)); n++; } } inline void _RMQ() { int i, j, p1, p2; for(i = 1;i <= n; ++i) RMQ[i][0] = i; for(j = 1;(1<<j) <= n; ++j) for(i = 1;i + (1<<(j-1))<= n; ++i) { p1 = RMQ[i][j-1]; p2 = RMQ[i+(1<<(j-1))][j-1]; if(Euler[p1].second < Euler[p2].second) RMQ[i][j] = p1; else RMQ[i][j] = p2; } Log2[1] = 0; for(i = 2;i <= n; ++i) Log2[i] = Log2[i>>1]+1; } inline int LCA(int X,int Y) { X = pos[X]; Y = pos[Y]; if(X > Y) swap(X,Y); int D = Y-X+1,L, p1, p2; L = Log2[D]; p1 = RMQ[X][L]; p2 = RMQ[X+D-(1<<L)][L]; if(Euler[p1].second < Euler[p2].second) return Euler[p1].first; return Euler[p2].first; } inline int Stramos(int p,int q) { int i; while(p && q) { for(i=0;(1<<i)<=p;i++); i--; q = stramos[i][q]; p-=(1<<i); } return q; } inline int Search(int x) { int Left = 0, Right = niv[x]-1, ret = 0; while(Left <= Right) { int mid = (Left+Right)/2; int st = Stramos(mid,x); //cout<<"Left = "<<Left<<" Right = "<<Right<<" mid = "<<mid<<" st="<<st<<" ret= "<<ret<<"\n"; if(st == 0){ Right = mid-1; continue; } if(Query(First[st])-Query(Last[st])>0) { ret = st; Right = mid-1; } else Left = mid+1; } return ret; } int main() { Read(); Euler.pb(mp(0,0)); _Euler(Root,0,0); Euler1(1,1); _RMQ(); for(int i=1;(1<<i)<=N;i++) for(int j=1;j<=N;j++) stramos[i][j] = stramos[i-1][stramos[i-1][j]]; Update(First[1],First[1],1); int boss = 1;/* for(int i=1;i<=n;++i) cout<<Euler[i].fi<<" "; cout<<"\n"; cout<<LCA(9,8)<<"\n";*/ //cout<<pos[8]<<" "<<pos[9]<<"\n"; //cout<<Query(First[1])-Query(Last[1])<<"\n\n"; //cout<<Stramos(1,4)<<"\n"; //cout<<Search(5)<<"\n"; for(int i=1;i<=M;++i) { int op, x, y; cin >> op; if(op==1) { cin >> x; Update(First[1],First[boss],-1); boss = x; Update(First[1],First[boss],1); } else { cin >> x >> y; int lca = LCA(x,y); //cout<<"x="<<x<<" y = "<<y<<" lca = "<<lca<<"\n"; if(Query(First[lca])-Query(Last[lca])==0) { if(lca == x || lca == y) { cout<<"-1\n"; continue; } cout<<lca<<"\n"; continue; } int a = Search(x); int b = Search(y); //cout<<x<<" "<<y<<" "<<boss<<" "<<a<<" "<<b<<"\n"; if(niv[a] < niv[b]) swap(a,b); if(a==x || a==y) cout<<"-1\n"; else cout<<a<<"\n"; } } return 0; }