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.*;

public class Main
{
    public static long pow(long a, long n, long mod) {
        //		a %= mod;
        long ret = 1;
        int x = 63 - Long.numberOfLeadingZeros(n);
        for (; x >= 0; x--) {
            ret = ret * ret % mod;
            if (n << 63 - x < 0)
                ret = ret * a % mod;
        }
        return ret;
    }
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public double rd() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, ri());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10,ri());
                    }
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        public int[] ra(int n)
        {
            int[] a = new int[n];
            for(int i = 0;i < n;i++)a[i] = ri();
            return a;
        }
        public long rl() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public int ri() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String rs() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return rs();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object...objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }
        public void println(Object...objects)
        {
            print(objects);
            writer.println();
        }
        public void close()
        {
            writer.close();
        }
        public void flush()
        {
            writer.flush();
        }
    }
    static class IOUtils
    {
        public static int[] readIntArray(InputReader in, int size)
        {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = in.ri();
            return array;
        }
    }
    static InputReader in ;
    static OutputWriter out ;
    public static void main(String [] args)
    {
        in = new InputReader(System.in) ;
        out = new OutputWriter(System.out) ;
//        int t = in.ri() ;
//        for (int i = 0; i <t ; i++)
            output() ;
        out.flush();
        out.close();
    }
    static int [] depth ;
    static int [][] spar ;
    static int [] centroid ;
    static int [] ans ;
    static void output()
    {
        int n = in.ri() ;
        int q = in.ri() ;
        int [] from = new int[n-1] ;
        int [] to = new int[n-1] ;
        for (int i = 0; i <(n-1) ; i++)
        {
            from[i] = in.ri()-1 ;
            to[i] = in.ri()-1 ;
        }
        int [][] g = packU(n,from,to) ;
        depth = parents3(g,0)[2] ;
        spar = logstepParents(parents3(g,0)[0]) ;
        centroid = buildCentroidTree(g) ;
        ans = new int[n] ;
        Arrays.fill(ans,(int)1e7);
        update(0);
        for (int i = 0; i <q ; i++)
        {
            int type = in.ri() ;
            int u = in.ri()-1 ;
            if(type==1)
            {
                update(u);
            }
            else
            {
                out.println(query(u));
            }
        }
    }
    static void update(int u)
    {
        int x = u ;
        while(u!=-1)
        {
//            out.println(u);
            ans[u] = Math.min(ans[u],dist(u,x,spar,depth)) ;
            u = centroid[u] ;
        }
    }
    static int query(int u)
    {
        int x = u ;
        int ret = (int)1e7 ;
        while(u!=-1)
        {
            ret = Math.min(ret,dist(x,u,spar,depth)+ans[u]) ;
            u = centroid[u] ;
        }
        return ret ;
    }
    static int dist(int a, int b, int[][] spar, int[] dep)
    {
        int lca = lca2(a, b, spar, dep);
        return dep[a]+dep[b]-2*dep[lca];
    }
    public static int lca2(int a, int b, int[][] spar, int[] depth)
    {
        if (depth[a] < depth[b]) {
            b = ancestor(b, depth[b] - depth[a], spar);
        } else if (depth[a] > depth[b]) {
            a = ancestor(a, depth[a] - depth[b], spar);
        }

        if (a == b)
            return a;
        int sa = a, sb = b;
        for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
                .numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
            if ((low ^ high) >= t) {
                if (spar[k][sa] != spar[k][sb]) {
                    low |= t;
                    sa = spar[k][sa];
                    sb = spar[k][sb];
                } else {
                    high = low | t - 1;
                }
            }
        }
        return spar[0][sa];
    }

    protected static int ancestor(int a, int m, int[][] spar) {
        for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
            if ((m & 1) == 1)
                a = spar[i][a];
        }
        return a;
    }

    public static int[][] logstepParents(int[] par) {
        int n = par.length;
        int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
        int[][] pars = new int[m][n];
        pars[0] = par;
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
            }
        }
        return pars;
    }


    public static int[][] parents3(int[][] g, int root) {
        int n = g.length;
        int[] par = new int[n];
        Arrays.fill(par, -1);

        int[] depth = new int[n];
        depth[0] = 0;

        int[] q = new int[n];
        q[0] = root;
        for (int p = 0, r = 1; p < r; p++) {
            int cur = q[p];
            for (int nex : g[cur]) {
                if (par[cur] != nex) {
                    q[r++] = nex;
                    par[nex] = cur;
                    depth[nex] = depth[cur] + 1;
                }
            }
        }
        return new int[][] { par, q, depth };
    }
    public static int[] buildCentroidTree(int[][] g) {
        int n = g.length;
        int[] ctpar = new int[n];
        Arrays.fill(ctpar, -1);
        buildCentroidTree(g, 0, new boolean[n], new int[n], new int[n], new int[n], ctpar);
        return ctpar;
    }
    private static int buildCentroidTree(int[][] g, int root, boolean[] sed, int[] par, int[] ord, int[] des, int[] ctpar)
    {
        ord[0] = root;
        par[root] = -1;
        int r = 1;
        for(int p = 0;p < r;p++) {
            int cur = ord[p];
            for(int nex : g[cur]){
                if(par[cur] != nex && !sed[nex]){
                    ord[r++] = nex;
                    par[nex] = cur;
                }
            }
        }
        int sep = -1;
        outer:
        for(int i = r-1;i >= 0;i--){
            int cur = ord[i];
            des[cur] = 1;
            for(int e : g[cur]){
                if(par[cur] != e && !sed[e])des[cur] += des[e];
            }
            if(r-des[cur] <= r/2){
                for(int e : g[cur]){
                    if(par[cur] != e && !sed[e] && des[e] >= r/2+1)continue outer;
                }
                sep = cur;
                break;
            }
        }
        sed[sep] = true;
        for(int e : g[sep]){
            if(!sed[e])ctpar[buildCentroidTree(g, e, sed, par, ord, des, ctpar)] = sep;
        }
        return sep;
    }
    static int[][] packU(int n, int[] from, int[] to)
    {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++)
        {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }
}