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 INF = 100000000;
    int N;
    ArrayList<Integer>[] A;
    boolean[] v;
    int[] par;

    int[] st;
    int[] prev;
    int[] sz;
    int[] lvl;

    int[][] dp;
    int maxk;

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

        v = new boolean[N];
        par = new int[N];
        st = new int[N];
        prev = new int[N];
        sz = new int[N];
        lvl = new int[N];
        separate(0);
        precalcLCA();

        int[] dist = new int[N];
        Arrays.fill(dist, INF);
        {
            int x = 0;
            for (int y = x; y != -1; y = par[y]) {
                int crtDist = calcDist(x, y);
                dist[y] = Math.min(dist[y], crtDist);
            }
        }
        while (M-- > 0) {
            int t = in.nextInt();
            int x = in.nextInt();
            x--;

            if (t == 1) {
                for (int y = x; y != -1; y = par[y]) {
                    int crtDist = calcDist(x, y);
                    dist[y] = Math.min(dist[y], crtDist);
                }
            }
            else {
                int ans = Integer.MAX_VALUE;
                for (int y = x; y != -1; y = par[y]) {
                    int crtDist = calcDist(x, y);
                    ans = Math.min(ans, dist[y] + crtDist);
                }
                out.println(ans);
            }
        }
    }

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

    private int calcLCA(int x, int y) {
        if (lvl[x] < lvl[y]) {
            int aux = x; x = y; y = aux;
        }
        for (int k = maxk - 1; k >= 0; k--) {
            int nx = dp[k][x];
            if (nx != -1 && lvl[nx] >= lvl[y]) {
                x = nx;
            }
        }

        if (x == y) {
            return x;
        }

        for (int k = maxk - 1; k >= 0; k--) {
            if (dp[k][x] != -1 && dp[k][y] != -1 && dp[k][x] != dp[k][y]) {
                x = dp[k][x];
                y = dp[k][y];
            }
        }
        return dp[0][x];
    }

    private void precalcLCA() {
        maxk = 0;
        while ((1 << maxk) < N) {
            maxk++;
        }
        dp = new int[maxk][N];

        int p = 0;
        st[p] = 0;
        prev[p] = -1;
        lvl[0] = 1;
        p++;
        for (int i = 0; i < p; i++) {
            int c = st[i];
            dp[0][c] = prev[i];
            for (int x : A[c]) {
                if (x != prev[i]) {
                    st[p] = x;
                    prev[p] = c;
                    lvl[x] = lvl[c] + 1;
                    p++;
                }
            }
        }

        for (int j = 1; j < maxk; j++) {
            for (int i = 0; i < N; i++) {
                if (dp[j - 1][i] == -1) {
                    dp[j][i] = -1;
                }
                else {
                    dp[j][i] = dp[j - 1][ dp[j - 1][i] ];
                }
            }
        }
    }

    private int separate(int node) {
        int p = 0;
        st[p] = node;
        prev[p] = -1;
        p++;
        for (int i = 0; i < p; i++) {
            int c = st[i];
            sz[c] = 1;
            for (int x : A[c]) {
                if (x != prev[i] && !v[x]) {
                    st[p] = x;
                    prev[p] = c;
                    p++;
                }
            }
        }

        int s = -1;
        for (int i = p - 1; i >= 0; i--) {
            int c = st[i];
            if (prev[i] != -1) {
                sz[prev[i]] += sz[c];
            }
            boolean ok = true;
            for (int x : A[c]) {
                if (!v[x] && x != prev[i] && sz[x] > p / 2) {
                    ok = false;
                    break;
                }
            }
            if (p - sz[c] > p / 2) {
                ok = false;
            }
            if (ok) {
                s = c;
                break;
            }
        }

        v[s] = true;
        par[s] = -1;
        for (int x : A[s]) {
            if (!v[x]) {
                int ns = separate(x);
                par[ns] = s;
            }
        }

        return s;
    }
}

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

}

