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

 1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 const int MAXN = 100011;16 const int inf = 1LL<<30;17 const int MAXM = 200011;18 #define RG register19 const int SIZE = 600;20 int n,m,ecnt,ans;21 int first[MAXN],to[MAXM],next[MAXM];22 int deep[MAXN],id[MAXN];23 int dui[MAXN],head,tail,dis[MAXN],ans_dis[MAXN];24 int D[MAXN*3],belong[MAXN*3];25 int ST[MAXN*3][20],mi[20];26 int stack[SIZE+12],top;27 28 inline int getint()29 {30        RG int w=0,q=0; RG char c=getchar();31        while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 32        while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;33 }34 35 inline void dfs(int x,int fa){36     D[++ecnt]=x; id[x]=ecnt;37     for(int i=first[x];i;i=next[i]) {38     RG int v=to[i]; if(v==fa) continue;39     deep[v]=deep[x]+1; dfs(v,x); 40     D[++ecnt]=x;41     }42 }43 44 inline void build(){45     belong[1]=0;  for(int i=2;i<=ecnt;i++) belong[i]=belong[i/2]+1;46     mi[0]=1; for(int i=1;i<=19;i++) mi[i]=mi[i-1]*2;47     for(int i=1;i<=ecnt;i++) ST[i][0]=D[i];48     for(int j=1;j<=19;j++) for(int i=1;i+mi[j-1]-1<=ecnt;i++) { if(deep[ST[i+mi[j-1]][j-1]]>deep[ST[i][j-1]]) ST[i][j]=ST[i][j-1]; else ST[i][j]=ST[i+mi[j-1]][j-1]; }49 }50 51 inline int lca(int x,int y){52     int f1=id[x],f2=id[y]; if(f1>f2) swap(f1,f2);53     int ll=f2-f1+1,lr=belong[ll]; 54     if(deep[ST[f1][lr]]>deep[ST[f2-(1<<lr)+1][lr]]) return ST[f2-(1<<lr)][lr];55     else return ST[f1][lr];56 }57 58 inline void work(){59     n=getint(); m=getint(); RG int x,y;60     for(RG int i=2;i<=n;i++) {61         x=getint(); y=getint();62     next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;63     next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;64     }65     ecnt=0; dfs(1,0); build();66     for(RG int i=1;i<=n;i++) ans_dis[i]=deep[i];67     RG int ljh,u;68     while(m--) {69     ljh=getint();70     if(ljh==2) {71         x=getint(); for(RG int i=1;i<=top;i++) ans_dis[x]=min(ans_dis[x],deep[x]+deep[stack[i]]-deep[lca(x,stack[i])]*2);72         printf("%d\n",ans_dis[x]);73     }74     else {75         x=getint(); if(x==0) continue; stack[++top]=x;76         if(top>=SIZE) {77         head=0; tail=0;    for(RG int i=1;i<=n;i++) dis[i]=inf;78         for(RG int i=1;i<=top;i++) dui[++tail]=stack[i],dis[stack[i]]=0;79         top=0;80         while(head<tail) {81             head++; u=dui[head]; ans_dis[u]=min(ans_dis[u],dis[u]);82             for(RG int i=first[u];i;i=next[i]) {83             RG int v=to[i];84             if(dis[v]==inf) {85                 dis[v]=dis[u]+1; dui[++tail]=v;86             }87             }88         }89         }90     }91     }92 }93 94 int main()95 {96   work();97   return 0;98 }