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.*;
import java.math.*;

import static java.lang.Math.*;

public class XeniaTree{
    static long mod = 1000000007L;
    static HashSet<Integer>[] g;
    static int[] d;
    static int[][] lca;
    static int[] sub;
    static int nodes;
    static int[] parent;
    static int[] res;

    public static void main(String[] args) throws Exception{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        
        int[] l1 = readArr(r);
        int n = l1[0];
        int m = l1[1];
        g = new HashSet[n];
        for(int i = 0; i < n; i++) g[i] = new HashSet<>();
        for(int i = 0; i < n - 1; i++){
            int[] li = readArr(r);
            g[li[0] - 1].add(li[1] - 1);
            g[li[1] - 1].add(li[0] - 1);
        }
        
        d = new int[n];
        lca = new int[31][n];
        dfs(0, -1);
        for(int i = 1; i < lca.length; i++){
            for(int j = 0; j < lca[0].length; j++){
                lca[i][j] = lca[i - 1][lca[i - 1][j]];
            }
        }
        sub = new int[n];
        parent = new int[n];
        res = new int[n];
        Arrays.fill(res, Integer.MAX_VALUE);

        decompose(0, -1);

        update(0);
        for(int i = 0; i < m; i++){
            int[] li = readArr(r);
            if(li[0] == 1){
                update(li[1] - 1);
            }else{
                System.out.println(query(li[1] - 1));
            }
        }

        r.close();
    }
    
    static void dfs(int u, int p){
        if(p >= 0){
            lca[0][u] = p;
            d[u] = d[p] + 1;
        }
        for(int v : g[u]){
            if(v == p) continue;
            dfs(v, u);
        }
    }

    static int lca(int u, int v){
        if(d[u] > d[v]){
            int t = u;
            u = v;
            v = t;
        }
        int depth = d[v] - d[u];
        for(int i = 0; i < lca.length; i++){
            if((depth & (1 << i)) != 0)
                v = lca[i][v];
        }
        if(u == v)
            return u;
        for(int i = lca.length - 1; i >= 0; i--){
            if(lca[i][u] != lca[i][v]){
                u = lca[i][u];
                v = lca[i][v];
            }
        }
        return lca[0][u];
    }

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

    static void dfs2(int u, int p){
        nodes++;
        sub[u] = 1;
        for(int v : g[u]){
            if(v == p) continue;
            dfs2(v, u);
            sub[u] += sub[v];
        }
    }

    static int centroid(int u, int p){
        for(int v : g[u]){
            if(v == p || sub[v] <= nodes / 2) continue;
            return centroid(v, u);
        }
        return u;
    }

    static void decompose(int u, int p){
        nodes = 0;
        dfs2(u, -1);
        int centroid = centroid(u, -1);
        if(p == -1)
            p = centroid;
        parent[centroid] = p;
        for(int v : g[centroid]){
            g[v].remove(centroid);
            decompose(v, centroid);
        }
        g[centroid].clear();
    }

    static void update(int u){
        int centroid = u;
        while(true){
            res[centroid] = min(res[centroid], dist(centroid, u));
            if(centroid == parent[centroid])
                break;
            centroid = parent[centroid];
        }
    }

    static int query(int u){
        int centroid = u;
        int ans = Integer.MAX_VALUE;
        while(true){
            if(res[centroid] != Integer.MAX_VALUE)
                ans = min(ans, dist(u, centroid) + res[centroid]);
            if(centroid == parent[centroid])
                break;
            centroid = parent[centroid];
        }
        return ans;
    }

    static int[] readArr(BufferedReader r) throws Exception{
        String[] l = r.readLine().split(" ");
        int[] a = new int[l.length];
        for(int i = 0; i < l.length; i++)
            a[i] = Integer.parseInt(l[i]);
        return a;
    }
    static long[] readLongArr(BufferedReader r) throws Exception{
        String[] l = r.readLine().split(" ");
        long[] a = new long[l.length];
        for(int i = 0; i < l.length; i++)
            a[i] = Long.parseLong(l[i]);
        return a;
    }
    static float[] readFloatArr(BufferedReader r) throws Exception{
        String[] l = r.readLine().split(" ");
        float[] a = new float[l.length];
        for(int i = 0; i < l.length; i++)
            a[i] = Float.parseFloat(l[i]);
        return a;
    }
    static double[] readDoubleArr(BufferedReader r) throws Exception{
        String[] l = r.readLine().split(" ");
        double[] a = new double[l.length];
        for(int i = 0; i < l.length; i++)
            a[i] = Double.parseDouble(l[i]);
        return a;
    }
    static long modPow(long a, long b, long mod){
        if(b == 0) return 1 % mod;
        if(a <= 1 || b == 1) return a % mod;
        long pow = modPow(a, b >> 1, mod);
        if((b & 1) != 0)
            return ((((a % mod) * pow) % mod) * pow) % mod;
        else
            return (pow * pow) % mod;
    }
    static int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
    static long gcd(long a, long b){return b == 0 ? a : gcd(b, a % b);}
    static class Pair{
        int a, b;
        Pair(int a, int b){
            this.a = a;
            this.b = b;
        }
    }
}