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.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

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

    static class EXeniaAndTree {
        int MAXN = 200005;
        int lgN = 21;
        PrintWriter out;
        InputReader in;
        EzIntArrayList[] tree = new EzIntArrayList[MAXN];
        int[] par = new int[MAXN];
        int[] sz = new int[MAXN];
        int[] dep = new int[MAXN];
        boolean[] off = new boolean[MAXN];
        int[] dist = new int[MAXN];
        int[][] anc = new int[lgN][MAXN];

        void dfs(int v, int p) {
            anc[0][v] = p;
            for (int i = 1; i < lgN; i++)
                anc[i][v] = anc[i - 1][anc[i - 1][v]];
            for (int i = 0; i < tree[v].size; i++) {
                int u = tree[v].get(i);
                if (u != p) {
                    dist[u] = dist[v] + 1;
                    dfs(u, v);
                }
            }
        }

        int LCA(int u, int v) {
            if (dist[u] < dist[v]) {
                int t = u;
                u = v;
                v = t;
            }
            int diff = dist[u] - dist[v];
            for (int i = lgN - 1; i >= 0; i--) {
                if (((1 << i) & diff) != 0) {
                    u = anc[i][u];
                }
            }
            if (u == v)
                return u;
            for (int i = lgN - 1; i >= 0; i--) {
                if (anc[i][u] > 0 && anc[i][u] != anc[i][v]) {
                    u = anc[i][u];
                    v = anc[i][v];
                }
            }
            return anc[0][u];
        }

        void calc_sz(int u, int p) {
            sz[u] = 1;
            for (int i = 0; i < tree[u].size; i++) {
                int v = tree[u].get(i);
                if (v != p && !off[v]) {
                    calc_sz(v, u);
                    sz[u] += sz[v];
                }
            }
        }

        int get_centroid(int u, int p, int cur_sz) {
            for (int i = 0; i < tree[u].size; i++) {
                int v = tree[u].get(i);
                if (v != p && !off[v]) {
                    if (sz[v] * 2 > cur_sz)
                        return get_centroid(v, u, cur_sz);
                }
            }
            return u;
        }

        void centroid_decompose(int u, int p) {
            calc_sz(u, u);
            int cen = get_centroid(u, u, sz[u]);
            off[cen] = true;
            par[cen] = p;
            if (p != -1)
                dep[cen] = dep[p] + 1;
            for (int i = 0; i < tree[cen].size; i++) {
                int v = tree[cen].get(i);
                if (!off[v])
                    centroid_decompose(v, cen);
            }
        }

        int dist(int u, int v) {
            int LCA = LCA(u, v);
            return dist[u] + dist[v] - 2 * dist[LCA];
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            int n = ni();
            int m = ni();
            par = new int[n];
            int i = 0;
            for (i = 0; i < n; i++) {
                tree[i] = new EzIntArrayList();
            }
            for (i = 0; i < n - 1; i++) {
                int u = ni() - 1;
                int v = ni() - 1;
                tree[u].add(v);
                tree[v].add(u);
            }
            Arrays.fill(par, -1);
            dfs(0, 0);
            centroid_decompose(0, -1);
            int[] sub_dist = new int[n];
            Arrays.fill(sub_dist, MAXN);
            int u = 0;
            while (u != -1) {
                sub_dist[u] = Math.min(sub_dist[u], dist(u, 0));
                u = par[u];
            }
            while (m-- > 0) {
                int type = ni();
                if (type == 1) {
                    u = ni() - 1;
                    int which = u;
                    while (u != -1) {
                        sub_dist[u] = Math.min(sub_dist[u], dist(u, which));
                        u = par[u];
                    }
                } else {
                    int ans = MAXN;
                    u = ni() - 1;
                    int which = u;
                    while (u != -1) {
                        ans = Math.min(ans, sub_dist[u] + dist(u, which));
                        u = par[u];
                    }
                    pn(ans);
                }
            }


        }

        int ni() {
            return in.nextInt();
        }

        void pn(long zx) {
            out.println(zx);
        }

        class EzIntArrayList implements EzIntList, EXeniaAndTree.EzIntStack {
            private static final int DEFAULT_CAPACITY = 10;
            private static final double ENLARGE_SCALE = 2.0;
            private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
            private static final int HASHCODE_MULTIPLIER = 0x01000193;
            private int[] array;
            private int size;

            public EzIntArrayList() {
                this(DEFAULT_CAPACITY);
            }

            public EzIntArrayList(int capacity) {
                if (capacity < 0) {
                    throw new IllegalArgumentException("Capacity must be non-negative");
                }
                array = new int[capacity];
                size = 0;
            }

            public EzIntArrayList(EXeniaAndTree.EzIntCollection collection) {
                size = collection.size();
                array = new int[size];
                int i = 0;
                for (EXeniaAndTree.EzIntIterator iterator = collection.iterator(); iterator.hasNext(); ) {
                    array[i++] = iterator.next();
                }
            }

            public EzIntArrayList(int[] srcArray) {
                size = srcArray.length;
                array = new int[size];
                System.arraycopy(srcArray, 0, array, 0, size);
            }

            public EzIntArrayList(Collection<Integer> javaCollection) {
                size = javaCollection.size();
                array = new int[size];
                int i = 0;
                for (int element : javaCollection) {
                    array[i++] = element;
                }
            }

            public int size() {
                return size;
            }

            public EXeniaAndTree.EzIntIterator iterator() {
                return new EzIntArrayListIterator();
            }

            public boolean add(int element) {
                if (size == array.length) {
                    enlarge();
                }
                array[size++] = element;
                return true;
            }

            public int get(int index) {
                if (index < 0 || index >= size) {
                    throw new IndexOutOfBoundsException("Index " + index + " is out of range, size = " + size);
                }
                return array[index];
            }

            private void enlarge() {
                int newSize = Math.max(size + 1, (int) (size * ENLARGE_SCALE));
                int[] newArray = new int[newSize];
                System.arraycopy(array, 0, newArray, 0, size);
                array = newArray;
            }

            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                EzIntArrayList that = (EzIntArrayList) o;

                if (size != that.size) {
                    return false;
                }
                for (int i = 0; i < size; i++) {
                    if (array[i] != that.array[i]) {
                        return false;
                    }
                }
                return true;
            }

            public int hashCode() {
                int hash = HASHCODE_INITIAL_VALUE;
                for (int i = 0; i < size; i++) {
                    hash = (hash ^ EXeniaAndTree.PrimitiveHashCalculator.getHash(array[i])) * HASHCODE_MULTIPLIER;
                }
                return hash;
            }

            public String toString() {
                StringBuilder sb = new StringBuilder();
                sb.append('[');
                for (int i = 0; i < size; i++) {
                    sb.append(array[i]);
                    if (i < size - 1) {
                        sb.append(", ");
                    }
                }
                sb.append(']');
                return sb.toString();
            }

            private class EzIntArrayListIterator implements EXeniaAndTree.EzIntIterator {
                private int curIndex = 0;

                public boolean hasNext() {
                    return curIndex < size;
                }

                public int next() {
                    if (curIndex == size) {
                        throw new NoSuchElementException("Iterator doesn't have more elements");
                    }
                    return array[curIndex++];
                }

            }

        }

        interface EzIntCollection {
            int size();

            EXeniaAndTree.EzIntIterator iterator();

            boolean equals(Object object);

            int hashCode();

            String toString();

        }

        interface EzIntIterator {
            boolean hasNext();

            int next();

        }

        interface EzIntStack extends EXeniaAndTree.EzIntCollection {
            int size();

            EXeniaAndTree.EzIntIterator iterator();

            boolean equals(Object object);

            int hashCode();

            String toString();

        }

        static class PrimitiveHashCalculator {
            private PrimitiveHashCalculator() {
            }

            public static int getHash(int x) {
                return x;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

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

        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

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

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static interface EzIntList {
    }
}

