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.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class XeniaAndTree {
    private static final int N = 100001;
    private static final int LOGN = 20;
    private static final int INF = 1000000000;
    private static int[] subSizeArr = new int[N];
    private static int[] parentArr = new int[N];
    private static int[] levelArr = new int[N];
    private static int[] ansArr = new int[N];
    private static ArrayList<Integer>[] graph = new ArrayList[N];
    private static int n, m;
    private static int numNodes;
    private static int[][] dp = new int[LOGN][N];

    private static int lca(int u, int v){
        if(levelArr[u]<levelArr[v]){
            int temp = u;
            u = v;
            v = temp;
        }
        int log = 1;
        for(;(1<<log) <= levelArr[u];log++);
        log--;
        for(int i=log;i>=0;i--){
            if((levelArr[u]-(1<<i))>=levelArr[v])
                u = dp[i][u];
        }
        if(u==v)
            return u;
        for(int i=log;i>=0;i--){
            if(dp[i][u]!=-1 && dp[i][u]!=dp[i][v]){
                u = dp[i][u];
                v = dp[i][v];
            }
        }
        return dp[0][u];
    }

    private static void dfs(int u){
        for(int i=0;i<graph[u].size();i++){
            int v = graph[u].get(i);
            if(v!=dp[0][u]){
                dp[0][v] = u;
                levelArr[v] = levelArr[u] + 1;
                dfs(v);
            }
        }
    }

    private static void preprocess(){
        levelArr[0] = 0;
        dp[0][0] = 0;
        dfs(0);
        for(int i=1;i<LOGN;i++){
            for(int j=0;j<n;j++){
                dp[i][j] = dp[i-1][dp[i-1][j]];
            }
        }
    }

    private static void calcSubSizes(int u, int p){
        subSizeArr[u] = 1;
        numNodes++;
        for(int i=0;i < graph[u].size();i++){
            int v = graph[u].get(i);
            if(v!=p){
                calcSubSizes(v,u);
                subSizeArr[u] += subSizeArr[v];
            }
        }
    }

    private static int findCentriod(int u, int p){
        for(int i=0;i<graph[u].size();i++){
            int v = graph[u].get(i);
            if(p!=v && subSizeArr[v]>numNodes/2)
                return findCentriod(v, u);
        }
        return u;
    }

    private static void decompose(int root, int parent){
        numNodes = 0;
        calcSubSizes(root,root);
        int centroid = findCentriod(root, root);
        if(parent==-1)
            parent = centroid;
        parentArr[centroid] = parent;
        for(int i=0;i<graph[centroid].size();i++){
            int v = graph[centroid].get(i);
            graph[v].remove(Integer.valueOf(centroid));
            decompose(v, centroid);
        }
        graph[centroid].clear();
    }

    private static int dist(int u, int v){
        return levelArr[u] + levelArr[v] - 2 * levelArr[lca(u,v)];
    }

    private static void update(int u){
        int x = u;
        while(true){
            ansArr[x] = Math.min(ansArr[x],dist(x,u));
            if(x == parentArr[x])
                break;
            x = parentArr[x];
        }
    }

    private static int query(int u){
        int x = u;
        int ret = INF;
        while(true){
            ret = Math.min(ret,ansArr[x]+dist(x,u));
            if(x == parentArr[x])
                break;
            x = parentArr[x];
        }
        return ret;
    }

    public static void main(String[] args){
        InputReader reader = new InputReader();
        PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
        // your program goes here
        n = reader.nextInt();
        m = reader.nextInt();
        for(int i=0;i<n;i++)
            graph[i] = new ArrayList<>();
        for(int i=0;i<n-1;i++){
            int u = reader.nextInt();
            int v = reader.nextInt();
            graph[u-1].add(v-1);
            graph[v-1].add(u-1);
        }
        preprocess();
        decompose(0,-1);
        for(int i=0;i<n;i++)
            ansArr[i] = INF;
        update(0);
        for(int i=0;i<m;i++){
            int type,val;
            type = reader.nextInt();
            val = reader.nextInt();
            if(type==1)
                update(val-1);
            else
                System.out.println(query(val-1));
        }
        writer.close();
    }
    static class InputReader{
        BufferedReader br;
        StringTokenizer tokenizer;

        InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next(){
            while(tokenizer==null || !tokenizer.hasMoreElements()){
                try{
                    tokenizer = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        public Integer nextInt(){
            return Integer.parseInt(next());
        }

        public Long nextLong(){
            return Long.parseLong(next());
        }

        public Double nextDouble(){
            return Double.parseDouble(next());
        }

        public String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}


