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.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — 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 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — an edge of the tree.

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

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

Output

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

Examples

Input

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


Output

0
3
2
import java.util.*;
import java.io.*;
public class code342E {

	static class LCA
	{
	    int[] first,depth;
	    static ArrayList<Integer> val;
	    static ArrayList<Integer> pos;
	    ArrayList<Integer>[] tree;
	    int[][] lookup;
	    ArrayList<Integer> array;
	    int N;
	    int cont;
	    public LCA(int n){
	    	N=n;
	        first=new int[N];
	        depth=new int[N];
	        tree=new ArrayList[N];
	        for(int i=0;i<N;i++){
	        	tree[i]=new ArrayList<>();
	        	first[i]=-1;
	        	depth[i]=-1;
	        }
	        val=new ArrayList<>();
	        pos=new ArrayList<>();
	    }

	    public void build(int root){
	    	cont=0;
	        walk(root, 0, -1);
	        depth[root]=0;
	        init(pos);
	    }
	    
	    public void anadir(int a,int b){
	    	tree[a].add(b);
	    	tree[b].add(a);
	    }

	    //dfs sobre el arbol llenando 3 arreglos (first,val,pos)
	    public void walk(int vertex,int p,int parent){
	        if (first[vertex]==-1){
	            first[vertex]=cont;
	            depth[vertex]=p;
	        }        
	        val.add(vertex);
	        pos.add(p);
	        ArrayList<Integer> childs=tree[vertex];
	        for(int i=0;i<childs.size();i++){
	        	int child=childs.get(i);
	            if(child!=parent){
	                cont++;
	                walk(child,p+1,vertex);
	                cont++;
	                val.add(vertex);
	                pos.add(p);
	            }
	        }
	    }

	    public void init(ArrayList<Integer> ar){        
	        array = ar;
	        lookup = new int[array.size()][(int)(Math.log(array.size())/Math.log(2))+1]; 
	        preprocess(array);
	    }

	    void preprocess(ArrayList<Integer> arr){
	        int n=arr.size();
	        for (int i = 0; i < n; i++)
	            lookup[i][0] = i;
	        for (int j=1; (1<<j)<=n; j++){
	            for (int i = 0; (i+(1<<j)-1)<n; i++){
	                if (arr.get(lookup[i][j - 1]) < arr.get(lookup[i+(1<<(j-1))][j-1]))
	                    lookup[i][j] = lookup[i][j - 1];
	                else
	                    lookup[i][j] = lookup[i+(1<<(j-1))][j-1];
	            }
	        }
	    }

	    public int spquery(int l, int r){
	        int j = (int)(Math.log((r-l)+1)/Math.log(2));
	        if (array.get(lookup[l][j])<=array.get(lookup[r-(int)Math.pow(2,j)+1][j]))
	            return lookup[l][j];
	        else
	            return lookup[r-(int)Math.pow(2,j)+1][j];
	    }

	    public int query(int l, int r){
	        if (first[l]<first[r])  return val.get(spquery(first[l],first[r]));
	        return val.get(spquery(first[r],first[l]));
	    }
	    
	    public int dist(int a,int b){
	    	return depth[a]+depth[b]-2*depth[query(a,b)];
	    }

	}
	static class CentroidDecomposition {		
		ArrayList<Integer>[] arbol,decomposedTree;
		int[] size;
		int[] centroidLevel;
		int[] parent;
		int V;
		public CentroidDecomposition(int N){
			V=N;
			arbol=new ArrayList[V];
			for(int i=0;i<N;i++){
				arbol[i]=new ArrayList<>();
			}
		}
		public void add(int a,int b){
			arbol[a].add(b);
			arbol[b].add(a);
		}
		public void centroidDecomposition(int v){
			size=new int[V];
			parent=new int[V];
			decomposedTree=new ArrayList[V];
			for(int i=0;i<decomposedTree.length;i++){
				parent[i]=-1;
				decomposedTree[i]=new ArrayList<>();
			}
			
			centroidLevel=new int[V];
			Arrays.fill(centroidLevel, -1);
			decompose(v,V,0);	
			
		}
		public int findCentroid(int v,int tam,int p){
			int res=v;
			
			ArrayList<Integer> hijos=arbol[v];
			for(int i=0;i<hijos.size() && res==v;i++){
				int hijo=hijos.get(i);
				if(hijo!=p && centroidLevel[hijo]==-1){
					if(size[hijo]>tam/2){
						res=findCentroid(hijo,tam,v);
					}
				}
			}
			
			return res;
		}
		public int decompose(int v,int tam, int level){
			
			getSize(v,-1);
			int centroid=findCentroid(v,tam,-1);
			getSize(centroid,-1);
			
			centroidLevel[centroid]=level;
			
			ArrayList<Integer> hijos=arbol[centroid];
			
			for(int i=0;i<hijos.size();i++){
				int hijo=hijos.get(i);
				if(centroidLevel[hijo]==-1){
					int next=decompose(hijo,size[hijo],level+1);
					parent[next]=centroid;
					decomposedTree[centroid].add(next);
					decomposedTree[next].add(centroid);
				}
			}
			
			return centroid;
			
		}
		public int getSize(int v,int p){
			ArrayList<Integer> hijos=arbol[v];
			size[v]=1;
			for(int i=0;i<hijos.size();i++){
				int hijo=hijos.get(i);
				if(hijo!=p && centroidLevel[hijo]==-1){
					size[v]+=getSize(hijo,v);
				}
			}
			return size[v];		
		}
	}

	static LCA lca;
	static CentroidDecomposition cd;
	static int[] res;
	public static void main(String[] args) throws Exception{
		BufferedReader bff=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter wff=new PrintWriter(System.out);
		String[] st=bff.readLine().split(" ");
		int V=Integer.parseInt(st[0]);
		int Q=Integer.parseInt(st[1]);
		cd=new CentroidDecomposition(V);
		lca=new LCA(V);
		for(int i=0;i<V-1;i++){
			st=bff.readLine().split(" ");
			int a=Integer.parseInt(st[0])-1;
			int b=Integer.parseInt(st[1])-1;
			cd.add(a, b);
			lca.anadir(a,b);
		}
		
		cd.centroidDecomposition(0);
		lca.build(0);
		
		res=new int[V];
		Arrays.fill(res, Integer.MAX_VALUE/2);
		update(0);
		for(int i=0;i<Q;i++){
			st=bff.readLine().split(" ");
			int type=Integer.parseInt(st[0]);
			int vertex=Integer.parseInt(st[1])-1;
			if(type==1){
				update(vertex);
			}
			else{
				wff.println(query(vertex));
			}
		}
		wff.flush();
	}
	public static int query(int vertex){
		int[] parent=cd.parent;
		int min=Integer.MAX_VALUE/2;
		int actual=vertex;
		while(actual!=-1){
			min=Math.min(min, lca.dist(vertex,actual)+res[actual]);
			actual=parent[actual];
		}
		return min;
	}
	public static void update(int vertex){
		int[] parent=cd.parent;
		int actual=vertex;
		while(actual!=-1){
			res[actual]=Math.min(res[actual], lca.dist(vertex, actual));
			actual=parent[actual];
		}
	}
}








