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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author fakhoury
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        EXeniaAndTree solver = new EXeniaAndTree();
        solver.solve(1, in, out);
        out.close();
    }

    static class EXeniaAndTree {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int q = in.nextInt();

            EXeniaAndTree.Vertex[] vertices = new EXeniaAndTree.Vertex[n];
            for (int i = 0; i < n; i++) {
                vertices[i] = new EXeniaAndTree.Vertex();
            }

            for (int i = 1; i < n; i++) {
                EXeniaAndTree.Vertex u = vertices[in.nextInt() - 1];
                EXeniaAndTree.Vertex v = vertices[in.nextInt() - 1];
                u.adj.add(v);
                v.adj.add(u);
            }

            vertices[0].dfsLCA(vertices[0]);
            for (int b = 1; b < 21; b++) {
                for (EXeniaAndTree.Vertex u : vertices) {
                    u.parent[b] = u.parent[b - 1].parent[b - 1];
                }
            }

            vertices[0].centroidDecomposition(null);
            vertices[0].update(vertices[0]);


            for (int i = 0; i < q; i++) {
                int op = in.nextInt();
                EXeniaAndTree.Vertex u = vertices[in.nextInt() - 1];
                if (op == 1) {
                    u.update(u);
                } else {
                    out.println(u.solve(u));
                }
            }
        }

        static class Vertex {
            List<EXeniaAndTree.Vertex> adj = new ArrayList<>();
            EXeniaAndTree.Vertex[] parent = new EXeniaAndTree.Vertex[21];
            boolean excluded = false;
            EXeniaAndTree.Vertex ancestor = null;
            int answer = (int) 1e8;
            int level = 0;
            int size;

            void calcSize(EXeniaAndTree.Vertex parent) {
                size = 1;
                for (EXeniaAndTree.Vertex v : adj)
                    if (v != parent && !v.excluded) {
                        v.calcSize(this);
                        size += v.size;
                    }
            }

            EXeniaAndTree.Vertex centroid(EXeniaAndTree.Vertex parent, int totalSize) {
                for (EXeniaAndTree.Vertex v : adj)
                    if (v != parent && !v.excluded) {
                        if (2 * v.size > totalSize) {
                            return v.centroid(this, totalSize);
                        }
                    }
                return this;
            }

            void centroidDecomposition(EXeniaAndTree.Vertex parent) {
                calcSize(null);
                EXeniaAndTree.Vertex u = centroid(null, size);
                u.excluded = true;

                if (parent != null) {
                    u.ancestor = parent;
                }

                for (EXeniaAndTree.Vertex v : u.adj)
                    if (!v.excluded) {
                        v.centroidDecomposition(u);
                    }
            }

            void dfsLCA(EXeniaAndTree.Vertex parent) {
                this.parent[0] = parent;
                for (EXeniaAndTree.Vertex v : adj)
                    if (v != parent) {
                        v.level = this.level + 1;
                        v.dfsLCA(this);
                    }
            }

            EXeniaAndTree.Vertex lca(EXeniaAndTree.Vertex v) {
                EXeniaAndTree.Vertex u = this;
                if (u.level < v.level) return v.lca(u);

                for (int b = 20; b >= 0; b--) {
                    if (u.level - (1 << b) >= v.level)
                        u = u.parent[b];
                }

                if (u == v) return u;

                for (int b = 20; b >= 0; b--) {
                    if (u.parent[b] != v.parent[b]) {
                        u = u.parent[b];
                        v = v.parent[b];
                    }
                }

                return u.parent[0];
            }

            int distance(EXeniaAndTree.Vertex u) {
                return level + u.level - 2 * this.lca(u).level;
            }

            void update(EXeniaAndTree.Vertex root) {
                answer = Math.min(answer, distance(root));
                if (ancestor != null)
                    ancestor.update(root);
            }

            int solve(EXeniaAndTree.Vertex root) {
                root.answer = Math.min(root.answer, root.distance(this) + answer);
                if (ancestor != null)
                    ancestor.solve(root);
                return root.answer;
            }

        }

    }

    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 close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.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 int nextInt() {
            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 boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

