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.*;
import java.math.*;
public class Solution{
    public static class SparseTree{
        int n;
        int root;
        int[][] dp;
        int[] depth;
        SparseTree(int n,int m,LinkedList<Integer>[] al){
            this.n = n;
            root = m;
            dp = new int[20][n];
            depth = new int[n];
            for(int i=0;i<20;i++) Arrays.fill(dp[i],-1);
            dfs(root,-1,al);
            depthDfs(root,-1,al);
        }
        
        void dfs(int m,int p,LinkedList<Integer>[] al){
            dp[0][m] = p;
            for(int i=1;i<20;i++){
                if(dp[i-1][m]!=-1) dp[i][m] = dp[i-1][dp[i-1][m]];
            }
            for(int u:al[m]){
                if(u!=p) dfs(u,m,al);
            }
        }
        void depthDfs(int cur, int prev,LinkedList<Integer>[] al){ 
            if(prev==-1) depth[cur] = 0;
            else depth[cur] = depth[prev] + 1; 
            for(int u:al[cur]){ 
                if(u != prev) depthDfs(u,cur,al); 
            } 
        } 
        int getDepth(int i){
            return depth[i];
        }
        int getParent(int node,int np){
            if(np==0) return node;
            if(np>depth[node]) return -1; 
            for (int i=0; i<20; i++) 
                if (((np>>i)&1)==1) 
                    node = dp[i][node];
            return node;
        }
        int getSameLevelTo(int u,int v){
            if(u==v||depth[u]==depth[v]) return u;
            if(depth[u]<depth[v]) return -1;
            int diff = depth[u] - depth[v]; 
            u = getParent(u,diff);
            return u;
        }
        int lca(int u, int v) { 
            int k = getSameLevelTo(u,v);
            if(k==-1) v = getSameLevelTo(v,u);
            else u = k;
            if (u == v) 
                return u;
            for (int i=19; i>=0; i--) 
                if (dp[i][u] != dp[i][v]){ 
                    u = dp[i][u]; 
                    v = dp[i][v]; 
                } 
          
            return dp[0][u]; 
        }
    }
    public static boolean[] red;
    public static LinkedList<Integer>[] al;
    public static int[] d;
    public static LinkedList<Integer> lred = new LinkedList<Integer>();
    public static int distance(int x,int v,SparseTree spt){
        int l = spt.lca(x,v);
        int dx = spt.getDepth(x);
        int dv = spt.getDepth(v);
        int dl = spt.getDepth(l);
        return dx-dl+dv-dl;
    }
    public static void dfs(int no,int p,int n){
        LinkedList<Integer> ll = new LinkedList<Integer>();
        //Arrays.fill(d,-1);
        for(int x:lred){
            ll.add(x);
            d[x] = 0;
        }
        //System.out.println(al[0]);
        int nb = 1;
        while(!ll.isEmpty()){
            int size = ll.size();
            for(int i=0;i<size;i++){
                int a = ll.pollFirst();
                for(int x:al[a]){
                    if(d[x]>nb){
                        d[x] = nb;
                        ll.addLast(x);
                    }
                }
            }
            nb++;
        }
        //for(int i=0;i<n;i++) System.out.print(d[i]+" ");
       // System.out.println("");
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Math.max(2,(int)Math.sqrt(m)+1);
        red = new boolean[n];
        red[0] = true;
        al = new LinkedList[n];
        for(int i=0;i<n;i++) al[i] = new LinkedList<Integer>();
        d = new int[n];
        Arrays.fill(d,n);
        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            al[a].add(b);
            al[b].add(a);
            //System.out.println();
        }
        lred.add(0);
        dfs(0,-1,n);
        lred.clear();
        SparseTree spt = new SparseTree(n,0,al);
        for(int i=1;i<=m;i++){
            if(i%k==0){
                dfs(0,-1,n);
                lred.clear();
            }
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken())-1;
            if(t==1&&red[v]==false){
                red[v] = true;
                lred.add(v);
            }else{
                int dist = d[v];
                for(int x:lred){
                    dist = Math.min(dist,distance(x,v,spt));
                }
                out.println(dist);
            }
        }
        out.flush();
   }
}