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.Arrays;
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 SQRT = 1000;
    private static final int INF = 1000000000;
    ArrayList<Integer>[] A;
    int[] reds;
    int r;
    int[] D;
    int[] Q;
    int N;

    int[] lvl;
    int[][] rmq;
    int[] lg;
    int[] euler;
    int[] pos;
    int e;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        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);
        }

        precalcLCA();

        Q = new int[N];
        D = new int[N];
        reds = new int[N];
        r = 0;
        reds[r++] = 0;
        int[] tempReds = new int[N];
        int tr;
        for (int i = 0; i < M; i += SQRT) {
            bfs();
            tr = 0;
            for (int j = 0; i + j < M && j < SQRT; j++) {
                int t = in.nextInt();
                int x = in.nextInt();
                x--;

                if (t == 1) {
                    tempReds[tr++] = x;
                    reds[r++] = x;
                }
                else {
                    int ans = D[x];
                    for (int k = 0; k < tr; k++) {
                        ans = Math.min(ans, dist(tempReds[k], x));
                    }
                    out.println(ans);
                }
            }
        }
    }

    private void precalcLCA() {
        euler = new int[4 * N];
        e = 0;
        lvl = new int[N];
        pos = new int[N];
        dfs(0, -1);

        lg = new int[e + 1];
        lg[1] = 0;
        for (int i = 2; i < e + 1; i++) {
            lg[i] = lg[i / 2] + 1;
        }

        int max = 0;
        while ((1 << max) <= e) {
            max++;
        }
        rmq = new int[max][e];
        for (int i = 0; i < e; i++) {
            rmq[0][i] = euler[i];
        }
        for (int j = 1; j < max; j++) {
            for (int i = 0; i + (1 << j) <= e; i++) {
                int a = rmq[j - 1][i];
                int b = rmq[j - 1][i + (1 << (j - 1))];
                if (lvl[a] < lvl[b]) {
                    rmq[j][i] = a;
                }
                else {
                    rmq[j][i] = b;
                }
            }
        }
    }

    private void dfs(int node, int prev) {
        lvl[node] = prev == -1 ? 1 : lvl[prev] + 1;
        pos[node] = e;
        for (int x : A[node]) {
            if (x != prev) {
                euler[e++] = node;
                dfs(x, node);
            }
        }
        euler[e++] = node;
    }

    private int dist(int x, int y) {
        int lca = calcLCA(x, y);
        return lvl[x] + lvl[y] - 2 * lvl[lca];
    }

    private int calcLCA(int x, int y) {
        x = pos[x];
        y = pos[y];
        if (x > y) {
            int aux = x; x = y; y = aux;
        }
        int k = lg[y - x + 1];
        int a = rmq[k][x];
        int b = rmq[k][y - (1 << k) + 1];
        if (lvl[a] < lvl[b]) {
            return a;
        }
        else {
            return b;
        }
    }

    private void bfs() {
        Arrays.fill(D, INF);
        int q = 0;
        for (int i = 0; i < r; i++) {
            D[reds[i]] = 0;
            Q[q++] = reds[i];
        }

        for (int i = 0; i < q; i++) {
            int p = Q[i];
            for (int x : A[p]) {
                if (D[p] + 1 < D[x]) {
                    D[x] = D[p] + 1;
                    Q[q++] = x;
                }
            }
        }
    }
}

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;
    }

}

