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.*; 

public class TestCodeforces 
{
	final static int n = 100009;                                  
	final static int logn =  20;                         
	
	public static int par[] = new int[n];                   
	public static int level[] = new int[n];                   
	public static int mat[][] = new int[n][logn];    
	public static int cenpar[] = new int[n];         
	public static int ans[] = new int[n];			  
	public static int size[] = new int[n];                
	public static int N,M;                                    
	public static int nn;								
	
	public static ArrayList<Integer> []arr = new ArrayList[n];  
	
	
	
	
	
	private static void pre()
	{
	    level[0] = 0;
	    par[0] = -1;
	    dfs1(0);                     

	    for(int i = 0;i < N;++i)                     
	        for(int j = 0;1<<j < N;++j)
	        mat[i][j] = -1;

	    for(int i = 0;i < N;++i)
	        mat[i][0] = par[i];          

	    for(int j = 1;1<<j < N;++j)                 
	        for(int i = 0;i < N;++i)
	            if(mat[i][j-1] != -1)
	                mat[i][j] = mat[mat[i][j-1]][j-1];
	}
	
	
	
	private static void dfs1(int u)               
	{
		Iterator<Integer> it = arr[u].iterator();                
	    while(it.hasNext())
	    {
	    	int temp = (int)it.next();
	        if(temp != par[u])                               
	        {
	            par[temp] = u;
	            level[temp] = level[u]+1;
	            dfs1(temp);                   
	        }
	    }
	}
	
	
	
	
	private static int lca(int u,int v)
	{
	    if(level[u] < level[v])                                        
	    {
	    	int temp = u;
	    	u = v;
	    	v = temp;
	    }
	    int log;
	    for(log = 1; 1 << log <= level[u];++log);                                          
	        --log;

	    for(int i = log;i >= 0;--i)										 
	        if(level[u] - (1<<i) >= level[v])
	            u = mat[u][i];

	    if(u == v)
	        return u;

	    for(int i = log;i >= 0;--i){                                     
	        if(mat[u][i] != -1 && mat[u][i] != mat[v][i]){
	            u = mat[u][i];
	    		v = mat[v][i];
	        }
	    }

	    return par[u];                          
	}
	
	
	
	private static void decomp(int root,int par)
	{
		nn = 0;
	    calculate(root,-1);            

	    int centroid = find(root,-1);      
	    
	    cenpar[centroid] = par;
	    Iterator<Integer> it = arr[centroid].iterator();       
	    while(it.hasNext())
	    {
	    	int temp = (int)it.next();
	        int ind = arr[temp].indexOf(centroid);    
	        arr[temp].remove(ind);
	        decomp(temp,centroid);    
	    }              
	}
	
	
	
	private static void calculate(int u,int par)
	{
	    size[u] = 1;                                   
	    ++nn;
	    Iterator<Integer> it = arr[u].iterator();
	    while(it.hasNext())                               
	    {
	    	int temp = (int)it.next();            
	        if(temp!= par)
	        {
	            calculate(temp,u);        
	            size[u] += size[temp];         
	        }
	    }
	}
	
	
	
	private static int find(int u,int par)
	{
		    Iterator<Integer> it = arr[u].iterator();
		    while(it.hasNext()){                                   
		    	int temp = (int)it.next();
		        if( temp!= par && size[temp] > nn/2)
		            return find(temp,u);
		    }
		 return u;
	}
	private static int dist(int p,int q)
	{
		return level[p]+level[q]-2*level[lca(p,q)];
	}
	private static void updateRed(int u)
	{
	    int x = u;
	    while(x != -1)
	    {
	    	int dist = dist(u,x);
	        ans[x] = dist < ans[x] ? dist : ans[x];	
	       
	        x = cenpar[x];        
	    }
	}
	
	private static int closestRed(int u)
	{
	    int par = u;
	    int res = 1000000000;
	    while(par != -1)
	    {
	    	int dist = dist(par,u);    
	        res = res < (dist + ans[par]) ? res : dist+ans[par];    
	        
	        par = cenpar[par];                 
	    }
	    return res;
	}

	

	
	public static void input()
	{
		Scanner sc = new Scanner(System.in);             
		N = sc.nextInt();
		M = sc.nextInt();
		int a,b;
	    
		for(int i = 0;i < N;++i)
			arr[i] = new ArrayList<Integer>();
		
		for(int i = 1;i < N;++i)                     
	    {
	       a = sc.nextInt();
	       b = sc.nextInt();
	      arr[a-1].add(b-1);
	      arr[b-1].add(a-1);
	    }
		
		pre();                   
	    decomp(0,-1);              
	    
	    for(int i = 0;i < N;++i)                 
	        ans[i] = 1000000000;

	    updateRed(0);          

	    
	    int q,u;
	    for(int i = 0;i < M;++i)
	    {
	        q = sc.nextInt();
	        u = sc.nextInt();
	        if(q == 1)
	            updateRed(u-1);
	        else
	           System.out.println(closestRed(u-1));
	    }
	}
	
	public static void main(String []args)
	{
		
		input();                                   
	}
}

  

	
 
 	

		
	
	


 

	



 
	
  		

 	
 


 
	  