#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define REP(I,A,B) for(int I=A,END=B;I<=END;I++)
#define RI(X) scanf("%d",&X)
#define RS(X) scanf("%s",&X)
#define GCH getchar()
#define T(X) tree[X]
#define MAX(A,B) (((A)>(B))?(A):(B))
#define MIN(A,B) (((A)<(B))?(A):(B))
#define MS(X,Y) memset(X,Y,sizeof(X))
#define MC(X,Y,var,len) memcpy((X),(Y),sizeof(var)*(len))
#define MAXN 100005
#define root 1
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
struct adj
{
int y;
int next;
}b[MAXN]={0};
struct node
{
int son;
int w;
int fa;
int top;
int size;
int deep;
}tree[MAXN]={0};
struct segment_tree
{
int first;
}st[MAXN<<1]={0};
int n,q,id,tot=0;
int head[MAXN]={0};
void open()
{
freopen("qtree3.in","r",stdin);
freopen("qtree3.out","w",stdout);
}
void close()
{
fclose(stdin);
fclose(stdout);
}
/*
white--0
black--1
*/
void add(int x,int y)
{
b[++tot].y=y;
b[tot].next=head[x];
head[x]=tot;
}
void dfs(int p) //fa son size deep
{
T(p).deep=T(T(p).fa).deep+1;
T(p).size=1;
for (int i=head[p];i;i=b[i].next)
if (b[i].y!=T(p).fa)
{
T(b[i].y).fa=p;
dfs(b[i].y);
if (T(T(p).son).size<T(b[i].y).size)
T(p).son=b[i].y;
T(p).size+=T(b[i].y).size;
}
}
void decomposition(int p)
{
T(p).w=++id;
if (T(p).son)
{
T(T(p).son).top=T(p).top;
decomposition(T(p).son);
}
for (int i=head[p];i;i=b[i].next)
if (b[i].y!=T(p).fa && b[i].y!=T(p).son)
{
T(b[i].y).top=b[i].y;
decomposition(b[i].y);
}
}
void up(int p)
{
int lch=p*2;
int rch=p*2+1;
if (st[lch].first==-1 && st[rch].first==-1)
return ;
if (st[lch].first!=-1)
{
if (st[p].first==-1 || T(st[lch].first).deep<T(st[p].first).deep)
st[p].first=st[lch].first;
}
if (st[rch].first!=-1)
{
if (st[p].first==-1 || T(st[rch].first).deep<T(st[p].first).deep)
st[p].first=st[rch].first;
}
}
void update(int p,int l,int r,int aim,int place)
{
if (l==r)
{
if (st[p].first>0)
st[p].first=-1;
else
st[p].first=place;
}
else
{
int mid=(l+r)/2;
if (st[p].first==place) //显然要重新第一个!
st[p].first=-1;
if (aim<=mid)
{
update(p*2,l,mid,aim,place);
}
else
{
update(p*2+1,mid+1,r,aim,place);
}
up(p); //更新本节点的答案
}
}
int que(int p,int l,int r,int ll,int rr)
{
if (l==ll && r==rr)
{
return st[p].first;
}
int mid=(l+r)/2;
if (rr<=mid)
{
return que(p*2,l,mid,ll,rr);
}
else if (mid<ll)
{
return que(p*2+1,mid+1,r,ll,rr);
}
else
{
int tmp1=que(p*2,l,mid,ll,mid);
int tmp2=que(p*2+1,mid+1,r,mid+1,rr);
if (tmp1==-1 && tmp2==-1)
return -1;
if (tmp1!=-1 && tmp2==-1)
return tmp1;
if (tmp1==-1 && tmp2!=-1)
return tmp2;
if (T(tmp1).deep>T(tmp2).deep)
return tmp2;
else
return tmp1;
}
}
void build_segment()
{
//这个偷点哈,反正都是白色
REP(i,1,id<<2)
{
st[i].first=-1;
}
}
void init()
{
int x,y;
RI(n);
RI(q);
REP(i,1,n-1)
{
RI(x);
RI(y);
add(x,y);
add(y,x);
}
T(root).fa=0;
dfs(root);
T(root).top=root;
decomposition(root);
build_segment();
}
int query(int u)
{
int fu=T(u).top;
int ans=-1,tmp;
while (fu!=1) //1是 root所在的重 链
{
tmp=que(1,1,id,T(fu).w,T(u).w);
if (tmp!=-1)
ans=tmp;
u=T(fu).fa;
fu=T(u).top;
}
tmp=que(1,1,id,1,T(u).w);
if (tmp!=-1)
return tmp;
return ans;
}
void work()
{
int way,aim;
REP(i,1,q)
{
RI(way);
RI(aim);
if (way)
{
printf("%d\n",query(aim));
}
else
{
update(1,1,id,T(aim).w,aim);
}
}
}
int main()
{
open();
init();
work();
close();
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8Y21hdGg+CiNkZWZpbmUgUkVQKEksQSxCKSBmb3IoaW50IEk9QSxFTkQ9QjtJPD1FTkQ7SSsrKQojZGVmaW5lIFJJKFgpIHNjYW5mKCIlZCIsJlgpCiNkZWZpbmUgUlMoWCkgc2NhbmYoIiVzIiwmWCkKI2RlZmluZSBHQ0ggZ2V0Y2hhcigpCiNkZWZpbmUgVChYKSB0cmVlW1hdCiNkZWZpbmUgTUFYKEEsQikgKCgoQSk+KEIpKT8oQSk6KEIpKQojZGVmaW5lIE1JTihBLEIpICgoKEEpPChCKSk/KEEpOihCKSkKI2RlZmluZSBNUyhYLFkpIG1lbXNldChYLFksc2l6ZW9mKFgpKQojZGVmaW5lIE1DKFgsWSx2YXIsbGVuKSBtZW1jcHkoKFgpLChZKSxzaXplb2YodmFyKSoobGVuKSkKI2RlZmluZSBNQVhOIDEwMDAwNQojZGVmaW5lIHJvb3QgMQojZGVmaW5lIGRlYnVnKC4uLikgZnByaW50ZihzdGRlcnIsX19WQV9BUkdTX18pCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBhZGoKewogIGludCB5OwogIGludCBuZXh0Owp9YltNQVhOXT17MH07CnN0cnVjdCBub2RlCnsKICBpbnQgc29uOwogIGludCB3OwogIGludCBmYTsKICBpbnQgdG9wOwogIGludCBzaXplOwogIGludCBkZWVwOwp9dHJlZVtNQVhOXT17MH07CnN0cnVjdCBzZWdtZW50X3RyZWUKewogIGludCBmaXJzdDsKfXN0W01BWE48PDFdPXswfTsKaW50IG4scSxpZCx0b3Q9MDsKaW50IGhlYWRbTUFYTl09ezB9OyAKdm9pZCBvcGVuKCkKewogIGZyZW9wZW4oInF0cmVlMy5pbiIsInIiLHN0ZGluKTsKICBmcmVvcGVuKCJxdHJlZTMub3V0IiwidyIsc3Rkb3V0KTsKfQp2b2lkIGNsb3NlKCkKewogIGZjbG9zZShzdGRpbik7CiAgZmNsb3NlKHN0ZG91dCk7Cn0KLyoKd2hpdGUtLTAKYmxhY2stLTEKKi8Kdm9pZCBhZGQoaW50IHgsaW50IHkpCnsKICBiWysrdG90XS55PXk7CiAgYlt0b3RdLm5leHQ9aGVhZFt4XTsKICBoZWFkW3hdPXRvdDsKfQp2b2lkIGRmcyhpbnQgcCkgIC8vZmEgc29uIHNpemUgZGVlcAp7CiAgVChwKS5kZWVwPVQoVChwKS5mYSkuZGVlcCsxOwogIFQocCkuc2l6ZT0xOwogIGZvciAoaW50IGk9aGVhZFtwXTtpO2k9YltpXS5uZXh0KQogICAgaWYgKGJbaV0ueSE9VChwKS5mYSkKICAgIHsKCSAgVChiW2ldLnkpLmZhPXA7CgkgIGRmcyhiW2ldLnkpOwoJICBpZiAoVChUKHApLnNvbikuc2l6ZTxUKGJbaV0ueSkuc2l6ZSkKCSAgICBUKHApLnNvbj1iW2ldLnk7CgkgIFQocCkuc2l6ZSs9VChiW2ldLnkpLnNpemU7Cgl9Cn0Kdm9pZCBkZWNvbXBvc2l0aW9uKGludCBwKQp7CiAgVChwKS53PSsraWQ7CiAgaWYgKFQocCkuc29uKQogIHsKICAgIFQoVChwKS5zb24pLnRvcD1UKHApLnRvcDsKICAgIGRlY29tcG9zaXRpb24oVChwKS5zb24pOwogIH0KICBmb3IgKGludCBpPWhlYWRbcF07aTtpPWJbaV0ubmV4dCkKICAgIGlmIChiW2ldLnkhPVQocCkuZmEgJiYgYltpXS55IT1UKHApLnNvbikKICAgIHsKCSAgVChiW2ldLnkpLnRvcD1iW2ldLnk7CgkgIGRlY29tcG9zaXRpb24oYltpXS55KTsKCX0KfQp2b2lkIHVwKGludCBwKQp7CiAgaW50IGxjaD1wKjI7CiAgaW50IHJjaD1wKjIrMTsKICBpZiAoc3RbbGNoXS5maXJzdD09LTEgJiYgc3RbcmNoXS5maXJzdD09LTEpCiAgICByZXR1cm4gOwogIGlmIChzdFtsY2hdLmZpcnN0IT0tMSkKICB7CiAgICBpZiAoc3RbcF0uZmlyc3Q9PS0xIHx8IFQoc3RbbGNoXS5maXJzdCkuZGVlcDxUKHN0W3BdLmZpcnN0KS5kZWVwKQogICAgICBzdFtwXS5maXJzdD1zdFtsY2hdLmZpcnN0OwogIH0KICBpZiAoc3RbcmNoXS5maXJzdCE9LTEpCiAgewogICAgaWYgKHN0W3BdLmZpcnN0PT0tMSB8fCBUKHN0W3JjaF0uZmlyc3QpLmRlZXA8VChzdFtwXS5maXJzdCkuZGVlcCkKICAgICAgc3RbcF0uZmlyc3Q9c3RbcmNoXS5maXJzdDsKICB9Cn0Kdm9pZCB1cGRhdGUoaW50IHAsaW50IGwsaW50IHIsaW50IGFpbSxpbnQgcGxhY2UpCnsKICBpZiAobD09cikKICB7CiAgICBpZiAoc3RbcF0uZmlyc3Q+MCkKICAgICAgc3RbcF0uZmlyc3Q9LTE7CiAgICBlbHNlCiAgICAgIHN0W3BdLmZpcnN0PXBsYWNlOwogIH0KICBlbHNlIAogIHsKICAgIGludCBtaWQ9KGwrcikvMjsKICAgIGlmIChzdFtwXS5maXJzdD09cGxhY2UpIC8v5pi+54S26KaB6YeN5paw56ys5LiA5LiqIQoJICBzdFtwXS5maXJzdD0tMTsgCiAgICBpZiAoYWltPD1taWQpCiAgICB7CgkgIHVwZGF0ZShwKjIsbCxtaWQsYWltLHBsYWNlKTsKCX0KCWVsc2UKCXsKCSAgdXBkYXRlKHAqMisxLG1pZCsxLHIsYWltLHBsYWNlKTsKCX0KCXVwKHApOyAvL+abtOaWsOacrOiKgueCueeahOetlOahiCAKICB9Cn0KaW50IHF1ZShpbnQgcCxpbnQgbCxpbnQgcixpbnQgbGwsaW50IHJyKQp7CiAgaWYgKGw9PWxsICYmIHI9PXJyKQogIHsKICAgIHJldHVybiBzdFtwXS5maXJzdDsKICB9CiAgaW50IG1pZD0obCtyKS8yOwogIGlmIChycjw9bWlkKQogIHsKICAgIHJldHVybiBxdWUocCoyLGwsbWlkLGxsLHJyKTsKICB9CiAgZWxzZSBpZiAobWlkPGxsKQogIHsKICAgIHJldHVybiBxdWUocCoyKzEsbWlkKzEscixsbCxycik7CiAgfQogIGVsc2UgCiAgewogICAgaW50IHRtcDE9cXVlKHAqMixsLG1pZCxsbCxtaWQpOwogICAgaW50IHRtcDI9cXVlKHAqMisxLG1pZCsxLHIsbWlkKzEscnIpOwogICAgaWYgKHRtcDE9PS0xICYmIHRtcDI9PS0xKQogICAgICByZXR1cm4gLTE7CiAgICBpZiAodG1wMSE9LTEgJiYgdG1wMj09LTEpCiAgICAgIHJldHVybiB0bXAxOwogICAgaWYgKHRtcDE9PS0xICYmIHRtcDIhPS0xKQogICAgICByZXR1cm4gdG1wMjsKICAgIGlmIChUKHRtcDEpLmRlZXA+VCh0bXAyKS5kZWVwKQogICAgICByZXR1cm4gdG1wMjsKICAgIGVsc2UgCiAgICAgIHJldHVybiB0bXAxOwogIH0KfQp2b2lkIGJ1aWxkX3NlZ21lbnQoKQp7CiAgLy/ov5nkuKrlgbfngrnlk4jvvIzlj43mraPpg73mmK/nmb3oibIgCiAgUkVQKGksMSxpZDw8MikKICB7CiAgICBzdFtpXS5maXJzdD0tMTsKICB9Cn0Kdm9pZCBpbml0KCkKewogIGludCB4LHk7CiAgUkkobik7CiAgUkkocSk7CiAgUkVQKGksMSxuLTEpCiAgewogICAgUkkoeCk7CiAgICBSSSh5KTsKICAgIGFkZCh4LHkpOwogICAgYWRkKHkseCk7CiAgfQogIFQocm9vdCkuZmE9MDsKICBkZnMocm9vdCk7CiAgVChyb290KS50b3A9cm9vdDsKICBkZWNvbXBvc2l0aW9uKHJvb3QpOyAKICBidWlsZF9zZWdtZW50KCk7Cn0KaW50IHF1ZXJ5KGludCB1KQp7CiAgaW50IGZ1PVQodSkudG9wOwogIGludCBhbnM9LTEsdG1wOyAKICB3aGlsZSAoZnUhPTEpIC8vMeaYryByb2905omA5Zyo55qE6YeNIOmTviAgCiAgewogICAgdG1wPXF1ZSgxLDEsaWQsVChmdSkudyxUKHUpLncpOwogICAgaWYgKHRtcCE9LTEpCiAgICAgIGFucz10bXA7CiAgICB1PVQoZnUpLmZhOwogICAgZnU9VCh1KS50b3A7CiAgfQogIHRtcD1xdWUoMSwxLGlkLDEsVCh1KS53KTsKICBpZiAodG1wIT0tMSkKICAgIHJldHVybiB0bXA7CiAgcmV0dXJuIGFuczsKfQp2b2lkIHdvcmsoKQp7CiAgaW50IHdheSxhaW07CiAgUkVQKGksMSxxKQogIHsKICAgIFJJKHdheSk7CiAgICBSSShhaW0pOwogICAgaWYgKHdheSkKICAgIHsKICAgICAgcHJpbnRmKCIlZFxuIixxdWVyeShhaW0pKTsKCX0KCWVsc2UgCgl7CgkgIHVwZGF0ZSgxLDEsaWQsVChhaW0pLncsYWltKTsKCX0KICB9Cn0KaW50IG1haW4oKQp7CiAgb3BlbigpOwogIGluaXQoKTsKICB3b3JrKCk7CiAgY2xvc2UoKTsKICByZXR1cm4gMDsKfQ==