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.util.resources.cldr.zh.CalendarData_zh_Hans_HK;

import java.io.*;
import java.text.DecimalFormat;
import java.util.*;
import java.awt.Point;
import java.math.BigInteger;

public class Newbie {

    static InputReader sc = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        solver s = new solver();
        int t = 1;
        while (t > 0) {
            s.solve();
            t--;
        }
        out.close();
    }

    static class InputReader {

        public BufferedReader br;
        public StringTokenizer token;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
            token = null;
        }

        public String sn() {
            while (token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return token.nextToken();
        }

        public int ni() {
            return Integer.parseInt(sn());
        }

        public String snl() throws IOException {
            return br.readLine();
        }

        public long nlo() {
            return Long.parseLong(sn());
        }

        public double nd() {
            return Double.parseDouble(sn());
        }

        public int[] na(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = sc.ni();
            return a;
        }

        public long[] nal(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = sc.nlo();
            return a;
        }
    }

    static class extra {

        static long fastexpo(long x, long y) {
            long res = 1;
            while (y > 0) {
                if ((y & 1) == 1) {
                    res *= x;
                }
                y = y >> 1;
                x = x * x;
            }
            return res;
        }

        static long lfastexpo(long x, long y, long p) {
            long res = 1;
            x = x % p;
            while (y > 0) {
                if ((y & 1) == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }
    }

    static int inf = 5000013;

    static class solver {
        DecimalFormat df = new DecimalFormat("0.00000000");
        extra e = new extra();
        long mod = (long) (1e9 + 9);
        int n, m, time;
        HashSet<Integer> list[];
        int dad[], st[], end[];
        int size[], level[];
        int up[][];

        boolean valid(int a, int b) {
            return st[a] <= st[b] && end[a] >= end[b];
        }

        void bfs(int s) {
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            level[s] = 0;
            boolean v[] = new boolean[n];
            v[s] = true;
            while (!q.isEmpty()) {
                int t = q.poll();
                for (int adj : list[t]) {
                    if (!v[adj]) {
                        v[adj] = true;
                        level[adj] = level[t] + 1;
                        q.add(adj);
                    }
                }
            }
        }

        int lca(int a, int b) {
            if (valid(a, b))
                return a;
            if (valid(b, a))
                return b;
            for (int i = 19; i >= 0; i--) {
                if (!valid(up[a][i], b))
                    a = up[a][i];
            }
            return up[a][0];
        }

        int dis(int u, int v) {
            return level[u] + level[v] - 2 * (level[lca(u, v)]);
        }

        int dfs(int s, int p) {
            size[s] = 1;
            for (int v : list[s]) {
                if (v != p)
                    size[s] += dfs(v, s);
            }
            return size[s];
        }

        void dfs1(int s, int p) {
            up[s][0] = p;
            for (int i = 1; i <= 19; i++)
                up[s][i] = up[up[s][i - 1]][i - 1];
            st[s] = ++time;
            for (int adj : list[s]) {
                if (adj != p)
                    dfs1(adj, s);
            }
            end[s] = ++time;
        }

        int dfs2(int s, int p, int n) {
            for (int v : list[s]) {
                if (v != p && size[v] > (n / 2))
                    return dfs2(v, s, n);
            }
            return s;
        }

        void build(int s, int p) {
            int n = dfs(s, p);
            int cen = dfs2(s, p, n);
            if (p == -1)
                p = cen;
            dad[cen] = p;
            for (Integer v : list[cen]) {
                list[v].remove(cen);
                build(v, cen);
            }
            list[cen].clear();
        }

        int ans[];

        void update(int u) {
            int x = u;
            ans[u] = 0;
            while (x != dad[x]) {
                x = dad[x];
                ans[x] = Math.min(ans[x], dis(x, u));
            }
        }

        int query(int u) {
            int x = u;
            int res = ans[u];
            while (x != dad[x]) {
                x = dad[x];
                res = Math.min(res, dis(x, u) + ans[x]);
            }
            return res;
        }

        void solve() {
            n = sc.ni();
            m = sc.ni();
            st = new int[n];
            level = new int[n];
            end = new int[n];
            size = new int[n];
            dad = new int[n];
            up = new int[n][20];
            ans = new int[n];
            list = new HashSet[n];
            for (int i = 0; i < n; i++) {
                ans[i] = 200000000;
                list[i] = new HashSet<>();
            }
            for (int i = 0; i < n - 1; i++) {
                int u = sc.ni() - 1;
                int v = sc.ni() - 1;
                list[u].add(v);
                list[v].add(u);
            }
            bfs(0);
            dfs1(0, 0);
            build(0, -1);
            update(0);
//            System.out.println(Arrays.toString(level));
            while (m-- > 0) {
                int t = sc.ni();
                if (t == 1) {
                    int u = sc.ni() - 1;
                    update(u);
                } else {
                    int u = sc.ni() - 1;
                    out.println(query(u));
                }
            }
        }
    }
}


