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 Sol1 
{
    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();                                   
    }
}