Description

Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.

The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.

Xenia needs to learn how to quickly execute queries of two types:

1. paint a specified blue node in red;
2. calculate which red node is the closest to the given one and print the shortest distance to the closest red node.

Your task is to write a program which will execute the described queries.

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵) — the number of nodes in the tree and the number of queries. Next n - 1 lines contain the tree edges, the i-th line contains a pair of integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — an edge of the tree.

Next m lines contain queries. Each query is specified as a pair of integers t_i, v_i (1 ≤ t_i ≤ 2, 1 ≤ v_i ≤ n). If t_i = 1, then as a reply to the query we need to paint a blue node v_i in red. If t_i = 2, then we should reply to the query by printing the shortest distance from some red node to node v_i.

It is guaranteed that the given graph is a tree and that all queries are correct.

For each second type query print the reply in a single line.

5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int inf = 1LL<<;

 const int MAXM = ;

 #define RG register

 const int SIZE = ;

 int n,m,ecnt,ans;

 int first[MAXN],to[MAXM],next[MAXM];

 int deep[MAXN],id[MAXN];

 int dui[MAXN],head,tail,dis[MAXN],ans_dis[MAXN];

 int D[MAXN*],belong[MAXN*];

 int ST[MAXN*][],mi[];

 int stack[SIZE+],top;

 inline int getint()

 {

        RG int w=,q=; RG char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;

 }

 inline void dfs(int x,int fa){

     D[++ecnt]=x; id[x]=ecnt;

     for(int i=first[x];i;i=next[i]) {

     RG int v=to[i]; if(v==fa) continue;

     deep[v]=deep[x]+; dfs(v,x);

     D[++ecnt]=x;

     }

 }

 inline void build(){

     belong[]=;  for(int i=;i<=ecnt;i++) belong[i]=belong[i/]+;

     mi[]=; for(int i=;i<=;i++) mi[i]=mi[i-]*;

     for(int i=;i<=ecnt;i++) ST[i][]=D[i];

     for(int j=;j<=;j++) for(int i=;i+mi[j-]-<=ecnt;i++) { if(deep[ST[i+mi[j-]][j-]]>deep[ST[i][j-]]) ST[i][j]=ST[i][j-]; else ST[i][j]=ST[i+mi[j-]][j-]; }

 }

 inline int lca(int x,int y){

     int f1=id[x],f2=id[y]; if(f1>f2) swap(f1,f2);

     int ll=f2-f1+,lr=belong[ll];

     if(deep[ST[f1][lr]]>deep[ST[f2-(<<lr)+][lr]]) return ST[f2-(<<lr)][lr];

     else return ST[f1][lr];

 }

 inline void work(){

     n=getint(); m=getint(); RG int x,y;

     for(RG int i=;i<=n;i++) {

         x=getint(); y=getint();

     next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;

     next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;

     }

     ecnt=; dfs(,); build();

     for(RG int i=;i<=n;i++) ans_dis[i]=deep[i];

     RG int ljh,u;

     while(m--) {

     ljh=getint();

     if(ljh==) {

         x=getint(); for(RG int i=;i<=top;i++) ans_dis[x]=min(ans_dis[x],deep[x]+deep[stack[i]]-deep[lca(x,stack[i])]*);

         printf("%d\n",ans_dis[x]);

     }

     else {

         x=getint(); if(x==) continue; stack[++top]=x;

         if(top>=SIZE) {

         head=; tail=;    for(RG int i=;i<=n;i++) dis[i]=inf;

         for(RG int i=;i<=top;i++) dui[++tail]=stack[i],dis[stack[i]]=;

         top=;

         while(head<tail) {

             head++; u=dui[head]; ans_dis[u]=min(ans_dis[u],dis[u]);

             for(RG int i=first[u];i;i=next[i]) {

             RG int v=to[i];

             if(dis[v]==inf) {

                 dis[v]=dis[u]+; dui[++tail]=v;

             }

             }

         }

         }

     }

     }

 }

 int main()

 {

   work();

   return ;

 }