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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class XeniaTree {
    
    int N = (int) 1e5 + 10;
    int LOG = 17;
    int INF = (int) 1e9;
    
    int[][] G;
    int[] sz = new int[N];
    int[] par = new int[N];
    boolean[] del = new boolean[N];
    
    int timer = 0;
    int[] tin = new int[N], tout = new int[N];
    int[] dep = new int[N];
    int[][] anc = new int[N][LOG];
    
    int[] f = new int[N];
    
    void solve() {
        int n = in.nextInt(), Q = in.nextInt();
        int[] fr = new int[n - 1], to = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            fr[i] = in.nextInt() - 1;
            to[i] = in.nextInt() - 1;
        }
        G = build_graph(n, fr, to);
        
        dfs(0, 0, 0);
        
        Arrays.fill(f, INF);
        dfs_mct(0, -1);
        update(0);
        
        while (Q-- > 0) {
            int t = in.nextInt(), v = in.nextInt() - 1;
            if (t == 1) {
                update(v);
            } else {
                out.println(query(v));
            }
        }
    }
    
    void update(int u) {
        int x = u;
        do {
            f[x] = Math.min(f[x], dist(x, u));
            x = par[x];
        } while (x >= 0);
    }
    
    int query(int u) {
        int ans = INF, x = u;
        do {
            ans = Math.min(ans, f[x] + dist(x, u));
            x = par[x];
        } while (x >= 0);
        return ans;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - dep[lca(u, v)] * 2;
    }
    
    int lca(int u, int v) {
        if (ancestor(u, v)) return u;
        if (ancestor(v, u)) return v;
        u = raise(u, v);
        return anc[u][0];
    }
    
    int raise(int u, int v) {
        for (int i = LOG - 1; i >= 0; i--) {
            if (!ancestor(anc[u][i], v)) u = anc[u][i];
        }
        return u;
    }
    
    boolean ancestor(int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }
    
    void dfs(int u, int p, int d) {
        tin[u] = timer++;
        dep[u] = d;
        anc[u][0] = p;
        for (int i = 1; i < LOG; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
        for (int v : G[u]) {
            if (v != p) dfs(v, u, d + 1);
        }
        tout[u] = timer++;
    }
    
    int dfs_mct(int u, int p) {
        // find the separator (centroid)
        dfs_sz(u, -1);
        int s = dfs_sep(u, -1, sz[u] / 2);
        par[s] = -1;
        // remove the separator and build centroid tree recursively
        del[s] = true;
        for (int v : G[s]) {
            if (!del[v]) par[dfs_mct(v, s)] = s;
        }
        return s;
    }
    
    int dfs_sep(int u, int p, int half) {
        for (int v : G[u]) {
            if (!del[v] && v != p) {
                if (sz[v] > half) return dfs_sep(v, u, half);
            }
        }
        return u;
    }
    
    int dfs_sz(int u, int p) {
        sz[u] = 1;
        for (int v : G[u]) {
            if (!del[v] && v != p) {
                sz[u] += dfs_sz(v, u);
            }
        }
        return sz[u];
    }
    
    int[][] build_graph(int n, int[] from, int[] to) {
        int[][] G = new int[n][];
        int[] cnt = new int[n];
        for (int i = 0; i < from.length; i++) {
            cnt[from[i]]++;
            cnt[to[i]]++;
        }
        for (int i = 0; i < n; i++) G[i] = new int[cnt[i]];
        for (int i = 0; i < from.length; i++) {
            G[from[i]][--cnt[from[i]]] = to[i];
            G[to[i]][--cnt[to[i]]] = from[i];
        }
        return G;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new XeniaTree().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
