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

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 2e9;
    static final long OO = (long) 4e18;
    static final int MOD = (int) 1e9 + 7;
    static final int LOGN = 20;

    static int n, m, timer = 0;
    static ArrayList<Integer>[] g;
    static int[] tin, tout, depth, d;
    static int[][] par;

    static void dfs(int u, int from) {
        tin[u] = timer++;
        par[u][0] = from;
        for (int i = 1; i < LOGN; i++)
            par[u][i] = par[par[u][i - 1]][i - 1];
        for (int v : g[u]) {
            if (v == from)
                continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
        tout[u] = timer++;
    }

    static boolean isPar(int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    static int lca(int u, int v) {
        if (isPar(u, v))
            return u;
        if (isPar(v, u))
            return v;
        for (int i = LOGN - 1; i >= 0; i--) {
            if (!isPar(par[u][i], v))
                u = par[u][i];
        }
        return par[u][0];
    }

    static int dist(int u, int v) {
        int lca = lca(u, v);
        return depth[u] + depth[v] - depth[lca] * 2;
    }

    static void bfs(ArrayList<Integer> reds) {
        LinkedList<Integer> q = new LinkedList<>();
        for (int u : reds) {
            q.add(u);
            d[u] = 0;
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : g[u]) {
                if (d[u] + 1 < d[v]) {
                    q.add(v);
                    d[v] = d[u] + 1;
                }
            }
        }
    }

    static void solve() {
        int n = in.nextInt();
        int m = in.nextInt();

        g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>());
        tin = new int[n];
        tout = new int[n];
        depth = new int[n];
        d = new int[n]; Arrays.fill(d, oo);
        par = new int[n][LOGN];

        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            g[u].add(v);
            g[v].add(u);
        }

        dfs(0, 0);

        ArrayList<Integer> reds = new ArrayList<>();
        reds.add(0);

        int block = (int) Math.sqrt(m);
        for (int i = 0; i < m; i++) {
            if (i % block == 0) {
                bfs(reds);
                reds.clear();
            }
            int type = in.nextInt();
            int u = in.nextInt() - 1;
            if (type == 1)
                reds.add(u);
            else {
                int ans = d[u];
                for (int v : reds)
                    ans = Math.min(ans, dist(u, v));
                out.println(ans);
            }
        }


    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("sometext.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

//        Thread thread = new Thread(null, () -> {
//            solve();
//        }, "Main", 1 << 28);
//        thread.start();
//        try {
//            thread.join();
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }

//        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }

    static void dbg(Object... args) {
        for (Object arg : args)
            out.print(" " + arg);
        out.flush();
    }

}