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 Main {
    static int n,m;
    static HashSet<Integer>graph[];
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        StringTokenizer st=new StringTokenizer(f.readLine());
        n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        graph=new HashSet[n];
        for(int i=0;i<n;i++){
            graph[i]=new HashSet<>();
        }
        for(int i=0;i<n-1;i++){
            st=new StringTokenizer(f.readLine());
            int a=Integer.parseInt(st.nextToken())-1;
            int b=Integer.parseInt(st.nextToken())-1;
            graph[a].add(b);
            graph[b].add(a);
        }
        ans=new int[n];
        parent=new int[n];
        subtree=new int[n];
        preProcess(graph,0,n);

        centroidDecomp(graph);
        Arrays.fill(ans,Integer.MAX_VALUE-300000);
        update(0,0);
        for(int i=0;i<m;i++){
            st=new StringTokenizer(f.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken())-1;
            if(a==1){
//                ans[b]=0;
                update(b,b);
            }
            else{
                int c= query(b,b);
                out.println(c);
            }
        }
        f.close();
        out.close();
    }
    static int[]ans;

    static void update(int curr,int orig){
        while(true){
            ans[curr]=Math.min(ans[curr],dist(curr,orig));
            curr=parent[curr];
            if(curr==-1){
                break;
            }
        }

    }
    static int query(int curr,int orig){
        int min=Integer.MAX_VALUE;
        while(true){
            min=Math.min(min,dist(orig,curr)+ans[curr]);
            curr=parent[curr];
            if(curr==-1)break;
        }

        return min;
    }

    static int dist(int a, int b){
        return depth[a]+depth[b]-2*depth[lca(a,b)];
    }
    static int[]parent;

    static void centroidDecomp(HashSet<Integer>[]graph){
        build(0,-1);

    }
    static void build(int curr,int prev){
//        int subtreeSize=subtree[curr];
        ss=0;
        subtreesize(curr,-1);
        int centroid=findCentroid(curr,prev,ss);

        parent[centroid]=prev;
        for(int i:graph[centroid]){

//            graph[centroid].remove(i);
            graph[i].remove(centroid);
            build(i,centroid);
        }
        graph[centroid].clear();;
    }
    static int ss=0;
    static void subtreesize(int curr,int par){
        subtree[curr]=1;
        ss++;
        for(int i:graph[curr]){
            if(i!=par){
                subtreesize(i,curr);
                subtree[curr]+=subtree[i];
            }
        }
    }
    static int findCentroid(int curr,int prev,int size){
//        Iterator<Integer>it=graph[curr].iterator();
//        while(it.hasNext()){
//
//        }
        for(int i: graph[curr]){
            if(i!=prev && subtree[i]>size/2 )return findCentroid(i,curr,size);
        }
        return curr;
    }
    static int len;
    static int[][] up;
    static int[] tin;
    static int[] tout;
    static int time;
    static int[]depth;
    static int[]subtree;
    static int dfs(HashSet<Integer>[] graph, int u, int p,int dept) {
        tin[u] = time++;
        up[0][u] = p;
        depth[u]=dept;
        for (int i = 1; i < len; i++)
            up[i][u] = up[i - 1][up[i - 1][u]];
        for (int v : graph[u]) {
            if (v != p) {
                dfs(graph, v, u, dept + 1);

            }
        }
        tout[u] = time++;
        return subtree[u]+=1;
    }

    static void preProcess(HashSet<Integer>[] tree, int root,int n) {

        len = 1;
        while ((1 << len) <= n) ++len;
        up = new int[len][n];
        tin = new int[n];
        tout = new int[n];
        depth=new int[n];
        dfs(tree, root, root,0);
    }

    static boolean isParent(int parent, int child) {
        return tin[parent] <= tin[child] && tout[child] <= tout[parent];
    }

    static public int lca(int a, int b) {
        if (isParent(a, b))
            return a;
        if (isParent(b, a))
            return b;
        //up[i][a]= from node a going up 2^i nodes

        for (int i = len - 1; i >= 0; i--)
            if (!isParent(up[i][a], b))
                a = up[i][a];
        return up[0][a];
    }
}