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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author George Marcus
 */
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);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private static final int INF = 1000000000;
    ArrayList<Integer>[] A;
    int[] subSize;
    int[] T;
    ArrayList<Integer>[] paths;
    int crtPathIdx;
    int[] inPath;
    int[] posPath;
    int[] tPath;
    int[] pathSize;
    int[] offset;
    int[] Amin;
    int[] Amax;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int N = in.nextInt();
        int M = in.nextInt();
        A = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < N - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            a--; b--;
            A[a].add(b);
            A[b].add(a);
        }

        crtPathIdx = 0;
        paths = new ArrayList[N];
        inPath = new int[N];
        T = new int[N];
        subSize = new int[N];
        dfs(0, -1);

        Amax = new int[4 * N];
        Amin = new int[4 * N];
        posPath = new int[N];
        tPath = new int[N];
        pathSize = new int[crtPathIdx];
        offset = new int[crtPathIdx];
        offset[0] = 0;
        for (int i = 0; i < crtPathIdx; i++) {
            pathSize[i] = paths[i].size();
            if (i > 0) {
                offset[i] = offset[i - 1] + 4 * pathSize[i - 1];
            }

            for (int left = 0, right = paths[i].size() - 1; left < right; left++, right--) {
                int aux = paths[i].get(left);
                paths[i].set(left, paths[i].get(right));
                paths[i].set(right, aux);
            }
            for (int j = 0; j < paths[i].size(); j++) {
                posPath[paths[i].get(j)] = j;
            }
            init(1, 0, pathSize[i] - 1, offset[i]);
        }

        for (int i = 0; i < N; i++) {
            int p = inPath[i];
            tPath[i] = T[paths[p].get(0)];
        }

        {
            int x = 0;
            int d = 0;
            while (x != -1) {
                int p = inPath[x];
                update(1, 0, pathSize[p] - 1, posPath[x], d, offset[p]);
                d += posPath[x] + 1;
                x = tPath[x];
            }
        }
        while (M-- > 0) {
            int t = in.nextInt();
            int x = in.nextInt();
            x--;

            if (t == 1) {
                int d = 0;
                while (x != -1) {
                    int p = inPath[x];
                    update(1, 0, pathSize[p] - 1, posPath[x], d, offset[p]);
                    d += posPath[x] + 1;
                    x = tPath[x];
                }
            }
            else {
                int extra = 0;
                int ans = INF;
                while (x != -1) {
                    int p = inPath[x];
                    int pos = posPath[x];
                    int left = queryMax(1, 0, pathSize[p] - 1, 0, pos, offset[p]);
                    int right = queryMin(1, 0, pathSize[p] - 1, pos, pathSize[p] - 1, offset[p]);
                    int dLeft = pos - left;
                    int dRight = right - pos;
                    int crt = Math.min(dLeft, dRight);
                    ans = Math.min(ans, extra + crt);

                    extra += pos + 1;
                    x = tPath[x];
                }

                out.println(ans);
            }
        }
    }

    private int queryMin(int k, int st, int dr, int a, int b, int o) {
        if (a <= st && dr <= b) {
            return Amin[o + k];
        }

        int m = (st + dr) / 2;
        int ret = INF;
        if (a <= m) {
            int crt = queryMin(2 * k, st, m, a, b, o);
            ret = Math.min(ret, crt);
        }
        if (b > m) {
            int crt = queryMin(2 * k + 1, m + 1, dr, a, b, o);
            ret = Math.min(ret, crt);
        }

        return ret;
    }

    private int queryMax(int k, int st, int dr, int a, int b, int o) {
        if (a <= st && dr <= b) {
            return Amax[o + k];
        }

        int m = (st + dr) / 2;
        int ret = -INF;
        if (a <= m) {
            int crt = queryMax(2 * k, st, m, a, b, o);
            ret = Math.max(ret, crt);
        }
        if (b > m) {
            int crt = queryMax(2 * k + 1, m + 1, dr, a, b, o);
            ret = Math.max(ret, crt);
        }

        return ret;
    }

    private void update(int k, int st, int dr, int pos, int val, int o) {
        if (st == dr) {
            Amax[o + k] = Math.max(Amax[o + k], st - val);
            Amin[o + k] = Math.min(Amin[o + k], st + val);
            return;
        }

        int m = (st + dr) / 2;
        if (pos <= m) {
            update(2 * k, st, m, pos, val, o);
        }
        else {
            update(2 * k + 1, m + 1, dr, pos, val, o);
        }

        Amin[o + k] = Math.min(Amin[o + 2 * k], Amin[o + 2 * k + 1]);
        Amax[o + k] = Math.max(Amax[o + 2 * k], Amax[o + 2 * k + 1]);
    }

    private void init(int k, int st, int dr, int o) {
        if (st == dr) {
            Amin[o + k] = INF;
            Amax[o + k] = -INF;
            return;
        }

        int m = (st + dr) / 2;
        init(2 * k, st, m, o);
        init(2 * k + 1, m + 1, dr, o);

        Amin[o + k] = Math.min(Amin[o + 2 * k], Amin[o + 2 * k + 1]);
        Amax[o + k] = Math.max(Amax[o + 2 * k], Amax[o + 2 * k + 1]);
    }

    private void dfs(int node, int prev) {
        T[node] = prev;
        subSize[node] = 1;

        int pmax = -1;
        for (int x : A[node]) {
            if (x != prev) {
                dfs(x, node);
                subSize[node] += subSize[x];
                if (pmax == -1 || subSize[x] > subSize[pmax]) {
                    pmax = x;
                }
            }
        }

        if (pmax == -1) {
            paths[crtPathIdx] = new ArrayList<Integer>();
            paths[crtPathIdx].add(node);
            inPath[node] = crtPathIdx;
            crtPathIdx++;
        }
        else {
            int p = inPath[pmax];
            paths[p].add(node);
            inPath[node] = p;
        }
    }
}

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 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() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        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;
    }

}

