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 = 21;

    static int n, m;
    static ArrayList<Integer>[] g;
    static int[] color, size, level, par;
    static int[][] d;
    static Treap[] ts;

    static class Treap {
        class Node {
            int x, y, val, minVal;
            Node left, right;

            Node(int x, int val) {
                this.x = x;
                y = rand.nextInt();
                this.val = val;
                minVal = val;
            }
        }
        Node root;

        int minVal(Node t) {
            return t == null ? oo : t.minVal;
        }
        void pull(Node t) {
            t.minVal = Math.min(t.val, Math.min(minVal(t.left), minVal(t.right)));
        }
        Node merge(Node t1, Node t2) {
            if (t1 == null)
                return t2;
            if (t2 == null)
                return t1;
            if (t1.y >= t2.y) {
                t1.right = merge(t1.right, t2);
                pull(t1);
                return t1;
            } else {
                t2.left = merge(t1, t2.left);
                pull(t2);
                return t2;
            }
        }
        Node[] split(Node t, int k) {
            if (t == null)
                return new Node[]{null, null};
            if (t.x <= k) {
                Node[] tt = split(t.right, k);
                t.right = tt[0];
                pull(t);
                return new Node[]{t, tt[1]};
            } else {
                Node[] tt = split(t.left, k);
                t.left = tt[1];
                pull(t);
                return new Node[]{tt[0], t};
            }
        }
        Node insert(Node t, Node t2) {
            if (t == null)
                return t2;
            if (t2.y >= t.y) {
                Node[] tt = split(t, t2.x);
                t2.left = tt[0];
                t2.right = tt[1];
                pull(t2);
                return t2;
            }
            if (t2.x < t.x)
                t.left = insert(t.left, t2);
            else
                t.right = insert(t.right, t2);
            pull(t);
            return t;
        }
        Node erase(Node t, int x) {
            if (t.x == x)
                return merge(t.left, t.right);
            if (x < t.x)
                t.left = erase(t.left, x);
            else
                t.right = erase(t.right, x);
            pull(t);
            return t;
        }

        void insert(int x, int val) {
            root = insert(root, new Node(x, val));
        }
        void erase(int x) {
            root = erase(root, x);
        }
        int minVal() {
            return minVal(root);
        }
    }

    static void dfs1(int u, int from) {
        size[u] = 1;
        for (int v : g[u]) {
            if (v == from || level[v] != -1)
                continue;
            dfs1(v, u);
            size[u] += size[v];
        }
    }

    static int dfs2(int u, int from, int sz) {
        for (int v : g[u]) {
            if (v == from || level[v] != -1)
                continue;
            if (size[v] > sz / 2)
                return dfs2(v, u, sz);
        }
        return u;
    }

    static int build(int u, int lvl) {
        dfs1(u, u);
        int center = dfs2(u, u, size[u]);
        level[center] = lvl;

        LinkedList<Integer> q = new LinkedList<>();
        q.add(center);
        d[center][lvl] = 0;
        while (!q.isEmpty()) {
            int fi = q.poll();
            for (int v : g[fi]) {
                if (level[v] != -1)
                    continue;
                if (d[fi][lvl] + 1 < d[v][lvl]) {
                    q.add(v);
                    d[v][lvl] = d[fi][lvl] + 1;
                }
            }
        }

        for (int v : g[center]) {
            if (level[v] != -1)
                continue;
            int cv = build(v, lvl + 1);
            par[cv] = center;
        }

        return center;
    }

    static void add(int u) {
        for (int lvl = level[u], c = u; lvl >= 0; lvl--, c = par[c])
            ts[c].insert(u, d[u][lvl]);
    }

    static int get(int u) {
        int res = oo;
        for (int lvl = level[u], c = u; lvl >= 0; lvl--, c = par[c])
            res = Math.min(res, d[u][lvl] + ts[c].minVal());
        return res;
    }


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

        g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>());
        color = new int[n];
        size = new int[n];
        level = new int[n]; Arrays.fill(level, -1);
        par = new int[n]; Arrays.fill(par, -1);
        d = new int[n][LOGN];
        for (int i = 0; i < n; i++)
            Arrays.fill(d[i], oo);
        ts = new Treap[n]; Arrays.setAll(ts, i -> new Treap());

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

        build(0, 0);

//        for (int i = 0; i < n; i++) {
//            dbg(i + 1, level[i], par[i] + 1, '\n');
//            for (int j = level[i]; j >= 0; j--)
//                dbg(d[i][j], '\n');
//        }

        color[0] = 1;
        add(0);

        for (int i = 0; i < m; i++) {
            int type = in.nextInt();
            int u = in.nextInt() - 1;
            if (type == 1) {
                if (color[u] == 0) {
                    color[u] = 1;
                    add(u);
                }
            } else if (type == 2)
                out.println(get(u));
        }


    }

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

}