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

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Trung Pham
 */
public class E {
    
    static int[] index = new int[100010];
    static int[] level = new int[100010];
    static int[] dep = new int[200010];
    static int[] floor_log = new int[200010];
    static int[] dist = new int[100010];
    static boolean[] red;
    static int pos;
    static ArrayList<Integer>[] map;
    static ArrayList<Integer> new_red = new ArrayList();
    static int[][] dp;
    
    public static void main(String[] args) {
        Scanner in = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int m = in.nextInt();
        map = new ArrayList[n];
        red = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList();
            index[i] = -1;
        }
        for (int i = 1; i < n; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            map[a].add(b);
            map[b].add(a);
        }
        for (int i = 0; i < 20; i++) {
            for (int j = 1 << i; j < (2 << i); j++) {
                if (j < 200010) {
                    floor_log[j] = i;
                }
            }
        }
        dfs(0, 0);
//        for(int i = 0; i < pos; i++){
//            System.out.print(dep[i] + " ");
//        }
//        System.out.println();
        pos++;
        int range = (int) (Math.log(pos) / Math.log(2));
        //System.out.println(range + " " + pos);
        dp = new int[pos][range + 1];
        for (int i = 0; i < pos; i++) {
            dp[i][0] = dep[i];
        }
        for (int j = 1; 1 << j < pos; j++) {
            for (int i = 0; i < pos; i++) {
                //System.out.println(pos + " " + range + " " + i + " " + j);
                int val = 1 << (j - 1);
                if (i + val >= pos) {
                    dp[i][j] = dp[i][j - 1];
                } else if (dp[i][j - 1] < dp[i + val][j - 1]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i + val][j - 1];
                }
            }
        }
        red[0] = true;  
        bfs();
        for (int i = 0; i < m; i++) {
            if (new_red.size() > 300) {
                new_red.clear();
                bfs();
            }
            int q = in.nextInt();
            int v = in.nextInt() - 1;
            if (q == 1) {
                red[v] = true;
                new_red.add(v);
            } else {
                out.println(minDist(v));
                // red.clear();
            }
        }
        out.close();
        //System.out.print(builder.toString());
    }
    
    static void bfs() {
        LinkedList<Integer> list = new LinkedList();
        for (int i = 0; i < red.length; i++) {
            if (red[i]) {
                dist[i] = 0;
                list.add(i);
            }
        }
        while (!list.isEmpty()) {
            int node = list.poll();
            for (int i = 0; i < map[node].size(); i++) {
                int next = map[node].get(i);
                if (dist[next] > dist[node] + 1) {
                    dist[next] = dist[node] + 1;
                    list.add(next);
                }
            }
        }
    }
    
    static int minDist(int node) {
        int result = dist[node];
        
        for (int i : new_red) {
            int total = level[node] + level[i];
            if (index[i] > index[node]) {
                result = Math.min(result, total - (2 * lca(index[node], index[i])));
            } else {
                result = Math.min(result, total - (2 * lca(index[i], index[node])));
            }
        }
        return result;
    }
    
    static int lca(int i, int j) {
        int k = floor_log[j - i + 1];
        int a = dp[i][k];
        int b = a;
        if (j + 1 - (1 << k) >= 0) {
            b = dp[j + 1 - (1 << k)][k];
        }
        return a < b ? a : b;
    }
    
    static void dfs(int node, int d) {
        index[node] = pos;
        level[node] = d;
        dep[pos] = d;
        pos++;
        for (int i = 0; i < map[node].size(); i++) {
            int next = map[node].get(i);
            if (index[next] == -1) {
                dfs(next, d + 1);
                dep[pos++] = d;
            }
        }
    }
    
    static class Scanner {
        
        BufferedReader br;
        StringTokenizer st;
        
        public Scanner() {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public String next() {
            
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        
        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
        
        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}
