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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class E {

    static StringTokenizer st;
    static BufferedReader br;
    static PrintWriter pw;
    static ArrayList<Integer>[]ages;
    static int[]dis, p;
    static boolean[]used;
    static int[]orderforlca;
    static int L, size;
    static int[][]sprase;
    static int[]first, two;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n = nextInt();
        int m = nextInt();
        ages = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            ages[i] = new ArrayList<Integer>();
        }
        orderforlca = new int[3*n+2];
        for (int i = 0; i < n-1; i++) {
            int v1 = nextInt();
            int v2 = nextInt();
            ages[v1].add(v2);
            ages[v2].add(v1);
        }
        used = new boolean[n+1];
        dis = new int[n+1];
        p = new int[n+1];
        dfs(1);
        first = new int[n+1];
        Arrays.fill(first, -1);
        while ((1 << (L+1)) <= size)
            L++;
        for (int i = 0; i < size; i++) {
            if (first[orderforlca[i]]==-1)
                first[orderforlca[i]] = i;
        }
        sprase = new int[L+1][size];
        for (int i = 0; i < size; i++) {
            sprase[0][i] = orderforlca[i];
        }
        for (int i = 1; i <= L; i++) {
            for (int j = 0; j+(1 << i) <= size; j++) {
                if (dis[sprase[i-1][j]] < dis[sprase[i-1][j+(1 << (i-1))]])
                    sprase[i][j] = sprase[i-1][j];
                else
                    sprase[i][j] = sprase[i-1][j+(1 << (i-1))];
            }
        }
        two = new int[size+1];
        for (int i = 1; i <= size; i++) {
            while (1 << (two[i]+1) <= i)
                two[i]++;
        }
        int sqrt = (int) Math.sqrt(m)+1;
        int[]d = new int[n+1];
        int INF = (int) 1e9;
        Arrays.fill(d, INF);
        d[1] = 0;
        int[]q = new int[n+1];
        int[]inblok = new int[sqrt+1];
        int cnt = 0;
        int head, tail;
        for (int i = 0; i < m; i++) {
            if (i % sqrt==0) {
                head = 0;
                tail = 0;
                for (int j = 1; j <= n; j++) {
                    if (d[j]==0)
                        q[++tail] = j;
                }
                while (head < tail) {
                    int v = q[++head];
                    for (int to : ages[v]) {
                        if (d[v]+1 < d[to]) {
                            d[to] = d[v]+1;
                            q[++tail] = to;
                        }
                    }
                }
                cnt = 0;
            }
            int t = nextInt();
            int v = nextInt();
            if (t==1) {
                d[v] = 0;
                inblok[cnt++] = v;
            }
            else {
                int ans = d[v];
                for (int j = 0; j < cnt; j++) {
                    int lca = lca(inblok[j], v);
                    ans = Math.min(ans, dis[v]-dis[lca]+dis[inblok[j]]-dis[lca]);
                }
                pw.println(ans);
            }
        }
        pw.close();
    }
    private static int lca(int a, int b) {
        int L = first[a], R = first[b];
        if (L > R) {
            int t = L;
            L = R;
            R = t;
        }
        int pow = two[R-L+1];
        if (dis[sprase[pow][L]] < dis[sprase[pow][R-(1 << pow)+1]])
            return sprase[pow][L];
        return sprase[pow][R-(1 << pow)+1];
    }

    private static void dfs(int v) {
        used[v] = true;
        orderforlca[size++] = v;
        for (int to : ages[v]) {
            if (to==p[v])
                continue;
            dis[to] = dis[v]+1;
            p[to] = v;
            dfs(to);
            orderforlca[size++] = v;
        }
    }
    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    private static String next() throws IOException {
        while (st==null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}
