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 sun.misc.*;

import java.awt.image.BufferedImage;
import java.io.*;
import java.util.*;
import java.util.Queue;
import java.util.concurrent.ExecutionException;


public class Main {
    final int maxn = 1 << 18;

    int n, m;
    int cnt;
    ArrayList<Integer>[] e = new ArrayList[maxn];
    ArrayList<Integer> a = new ArrayList<Integer>();
    int t[] = new int[maxn], v[] = new int[maxn];
    int L[] = new int[maxn], R[] = new int[maxn], h[] = new int[maxn];
    int isRed[] = new int[maxn];

    void dfs(int v, int p, int H) {
        L[v] = cnt++;
        R[v] = L[v];
        h[v] = H;
        a.add(H);
        for (int i = 0; i < e[v].size(); i++) {
            int to = e[v].get(i);
            if (to == p) continue;
            dfs(to, v, H + 1);
            R[v] = cnt++;
            a.add(H);
        }
    }

    int mn[][] = new int[18][1 << 18];
    int pw[] = new int[1 << 18];
    void build() {
        int curpw = 0, curi = 1;
        while (curi < maxn) {
            if (curi == (1 << curpw) * 2) curpw++;
            pw[curi++] = curpw;
        }

        for (int i = 0; i < cnt; i++) mn[0][i] = a.get(i);
        for (int j = 1; j < 18; j++) {
            for (int i = 0; i + (1 << j) <= cnt; i++) {
                mn[j][i] = Math.min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    int dist[] = new int[maxn];
    int q[] = new int[maxn], ql, qr;

    void bfs() {
        ql = 0;
        qr = -1;
        for (int i = 1; i <= n; i++) if (isRed[i] == 1) {
            dist[i] = 0;
            q[++qr] = i;
        } else dist[i] = maxn;

        while (ql <= qr) {
            int v = q[ql++];
            for (int i = 0; i < e[v].size(); i++) {
                int to = e[v].get(i);
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    q[++qr] = to;
                }
            }
        }
    }

    int getmin(int l, int r) {
        int j = pw[r - l + 1];
        return Math.min(mn[j][l], mn[j][r - (1 << j) + 1]);
    }

    int b[] = new int[maxn], szb;

    public void Run() {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        for (int i = 1; i <= n; i++) e[i] = new ArrayList<Integer>();
        m = in.nextInt();
        for (int i = 1; i < n; i++) {
            int u, v;
            u = in.nextInt();
            v = in.nextInt();
            e[u].add(v);
            e[v].add(u);
        }
        for (int i = 0; i < m; i++) {
            t[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        isRed[1] = 1;

        dfs(1, -1, 0);
        build();

        int K = 1000;
        for (int l = 0; l < m; l += K) {
            int r = Math.min(l + K - 1, m - 1);
            bfs();
            szb = 0;
            for (int i = l; i <= r; i++) {
                if (t[i] == 1) {
                    b[szb++] = v[i];
                    isRed[v[i]] = 1;
                }
                if (t[i] == 2) {
                    int ans = dist[v[i]];
                    for (int j = 0; j < szb; j++) {
                        ans = Math.min(ans, -2 * getmin(Math.min(L[v[i]], L[b[j]]), Math.max(R[v[i]], R[b[j]])) + h[v[i]] + h[b[j]]);
                    }
                    System.out.println(ans);
                }
            }
        }
    }

    public static void main(String[] args) {
        new Main().Run();
    }
}

class Scanner {
    BufferedReader in;
    StringTokenizer tok;

    public Scanner(InputStream in) {
        this.in = new BufferedReader(new InputStreamReader(in));
        tok = new StringTokenizer("");
    }

    private String tryReadNextLine() {
        try {
            return in.readLine();
        } catch (Exception e) {
            throw new InputMismatchException();
        }
    }

    public String nextToken() {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(next());
        }
        return tok.nextToken();
    }

    public String next() {
        String newLine = tryReadNextLine();
        if (newLine == null)
            throw new InputMismatchException();
        return newLine;
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

}
