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.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        solution.run();
    }

    int parseInt(StringTokenizer stok) {
        return Integer.parseInt(stok.nextToken());
    }

    int parseInt(String string) {
        return Integer.parseInt(string);
    }

    List<Integer>[] g;
    int[][] p;
    int[] tIn;
    int[] tOut;
    int[] hg;
    int timer;
    int lh;

    int log2(int n) {
        int p = 0;
        int b = 1;
        while (b <= n) {
            b *= 2;
            ++p;
        }
        return p - 1;
    }

    void dfs(int v, int parent, int h) {
        hg[v] = h;
        tIn[v] = timer++;
        p[v][0] =  parent;
        for (int i = 1; i <= lh; ++i)
            p[v][i] = p[p[v][i - 1]][i - 1];
        for (int i = 0; i < g[v].size(); ++i) {
            int to = g[v].get(i);
            if (to != parent) {
                dfs(to, v, h + 1);
            }
        }
        tOut[v] = timer++;
    }

    boolean isAncestor(int v, int candidate) {
        return tIn[candidate] <= tIn[v] && tOut[v] <= tOut[candidate];
    }

    int lca(int x, int y) {
        if (isAncestor(x, y))
            return y;
        if (isAncestor(y, x))
            return x;
        for (int l = lh; l >= 0; --l)
            if (!isAncestor(y, p[x][l]))
                x = p[x][l];
        return p[x][0];
    }

    int distance(int x, int y) {
        int ancestor = lca(x, y);
        return hg[x] + hg[y] - 2 * hg[ancestor];
    }

    int[] painted;
    int paintedTop;
    int[] d;
    int distanceToPainted(int v) {
        int res = d[v];
        for (int i = 0; i < paintedTop; ++i)
            res = Math.min(res, distance(v, painted[i]));
        return res;
    }

    void relax() {
        Deque<Integer> deq = new ArrayDeque<Integer>();
        for (int i = 0; i < paintedTop; ++i) {
            int v = painted[i];
            deq.addLast(v);
            d[v] = 0;
        }
        paintedTop = 0;
        while (deq.size() > 0) {
            int from = deq.pollFirst();
            int dval = d[from] + 1;
            for (int i = 0; i < g[from].size(); ++i) {
                int to = g[from].get(i);
                if (d[to] > dval) {
                    d[to] = dval;
                    deq.addLast(to);
                }
            }
        }
    }

    private void run() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stok = new StringTokenizer(reader.readLine());
        int n = parseInt(stok);
        int m = parseInt(stok);
        g = new List[n];
        lh = log2(n);
        p = new int[n][lh + 1];
        tIn = new int[n];
        tOut = new int[n];
        hg = new int[n];
        d = new int[n];
        Arrays.fill(d, Integer.MAX_VALUE);
        timer = 1;
        for (int i = 0; i < g.length; ++i)
            g[i] = new ArrayList<Integer>();
        for (int i = 1; i < n; ++i) {
            stok = new StringTokenizer(reader.readLine());
            int x = parseInt(stok);
            int y = parseInt(stok);
            --x;
            --y;
            g[x].add(y);
            g[y].add(x);
        }
        dfs(0, 0, 0);
        int sqm = (int) Math.sqrt(m);
        painted = new int[sqm];
        painted[0] = 0;
        paintedTop = 1;
        for (int i = 0; i < m; ) {
            relax();
            int end = Math.min(i + sqm, m) - 1;
            for (; i <= end; ++i) {
                stok = new StringTokenizer(reader.readLine());
                int t = parseInt(stok);
                int v = parseInt(stok);
                --v;
                if (t == 1) {
                    painted[paintedTop++] = v;
                } else {
                    System.out.println(distanceToPainted(v));
                }
            }
        }
    }
}
