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
/**
 * Created by Aminul on 7/23/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF342E {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), q = in.nextInt();
        List<Integer> g[] = genList(n+1);
        for (int i = 1; i <= n-1; i++) {
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v); g[v].add(u);
        }
        
        nearest = new int[n+1]; Arrays.fill(nearest, (int)1e9);
        lca = new LCASparseTable(g, 1); 
       
        Centroid_Decomposition centroid = new Centroid_Decomposition(g, 1);
        centroid.update(1);

        for (int i = 1; i <= q; i++) {
            int tp = in.nextInt(), u = in.nextInt();
            if(tp == 1) centroid.update(u);
            else pw.println(centroid.query(u));
        }

        pw.close();
    }

    static LCASparseTable lca;

    static int [] nearest;

    static class Centroid_Decomposition{
        List<Integer> g[];
        int [] size, par;
        boolean [] vis;

        Centroid_Decomposition(List<Integer> g[], int root){ // 1-based indexed, root = 1
            this.g = g;
            int n = g.length;
            size = new int[n]; par = new int[n];
            vis = new boolean[n];
            calcSize(root, 0);
            decompose(root, 0);
        }

        int calcSize(int u, int p) {
            size[u] = 1;
            for (int v : g[u]) {
                if (v != p) {
                    size[u] += calcSize(v, u);
                }
            }
            return size[u];
        }

        void decompose(int u, int p) {
            int max = 0, v = -1;
            for (int x : g[u]) {
                if (!vis[x] && size[x] > max) {
                    max = size[x];
                    v = x;
                }
            }
            while (max > size[u] / 2) {
                int t = size[v];
                size[v] = size[u];
                size[u] = size[v] - t;
                u = v;
                max = 0;
                for (int x : g[u]) {
                    if (!vis[x] && size[x] > max) {
                        max = size[x];
                        v = x;
                    }
                }
            }
            par[u] = p;
            vis[u] = true;
            for (int x : g[u]) {
                if (!vis[x]) {
                    decompose(x, u);
                }
            }
        }

        void update(int u){
            for(int v = u; v != 0; v = par[v]) {
                int dist = lca.dist(u, v);
                nearest[v] = min(nearest[v], dist);
            }
        }

        int query(int u){
            int min = Integer.MAX_VALUE;
            for(int v = u; v != 0; v = par[v]) {
                int dist = lca.dist(u, v);
                min = min(min, dist + nearest[v]);
            }
            return min;
        }

    }


    static class LCASparseTable {
        int log, time;
        int[][] up; // IMPORTANT : fill up[][] array with root, not required if root is 0.
        int[] tin, tout, level;
        List<Integer>[] tree;

        public LCASparseTable(List<Integer>[] tree, int root) {
            this.tree = tree;
            int n = tree.length;
            log = 1;
            while ((1 << log) <= n) ++log;
            up = new int[log][n]; for(int a[] : up) Arrays.fill(a, root);
            tin = new int[n];
            tout = new int[n];
            level = new int[n];
            dfs(root, root);
        }

        void dfs( int u, int p) {
            level[u] = 1 + level[p];
            tin[u] = time++;
            up[0][u] = p;
            for (int i = 1; i < log; i++)
                up[i][u] = up[i - 1][up[i - 1][u]];
            for (int v : tree[u])
                if (v != p)
                    dfs(v, u);
            tout[u] = time++;
        }

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

        public int dist(int a, int b){
            int lca = lca(a, b);
            return level[a] + level[b] - (2*level[lca]);
        }

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

    static <T>List<T>[] genList(int n){
        List<T> list[] = new List[n];
        for(int i = 0; i < n; i++) list[i] = new ArrayList<T>();
        return list;
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}