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 static java.lang.Math.*;




public class Main
{
    
    public static void main(String[] args)
    {

        FastInput input = new FastInput(System.in);
        PrintWriter output =  new PrintWriter(System.out);
        
        int n,m,a,b,t,v;
        
        n = input.readInt();
        m = input.readInt();
        
        Tree tree = new Tree(n, m);
        
        for (int i = 1; i < n; i++)
        {
            a = input.readInt();
            b = input.readInt();
            
            tree.addEdge(a, b);
        }
        
        tree.initializeTree();
        
        for (int i = 0; i < m; i++)
        {
            t = input.readInt();
            v = input.readInt();
            
            if (t == 1)
                tree.set(v);
            else
                output.println(tree.query(v));
            

        }
        
        input.close();
        output.close();
        
    }
}


class FastInput
{


        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;


        public FastInput(InputStream userInputStream)
        {
            this.stream = userInputStream;

        }


        public int readChar()
        {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars)
            {

                curChar = 0;

                try
                {
                    numChars = stream.read(buf);
                } 
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;

            }

            return buf[curChar++];

        }


        public boolean isSpaceChar(int c) 
        {

                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;

        }

        
        public int readInt()
        {

            int c = readChar();
            int sgn = 1;
            
            while (isSpaceChar(c))
                c = readChar();
            
            if (c == '-' )
            {
                sgn = -1;
                c = readChar();

            }

            int res = 0;

            do {

                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = readChar();

            } while (!isSpaceChar(c));

            return res * sgn;

        }

    
        public void close()
        {
                try
                {
                    stream.close();
                }
                catch(IOException ex)
                {
                    ex.printStackTrace();
                    
                }
        }
        
        

}



class Node 
{
    int v;
    Node next;
    
    Node(int v)
    {
        this.v = v;
    }

}

class Tree
{
        
     int noOfVertices, noOfQueries;
     ArrayList<Node> adjList;  //Adjacency list
     int[] dist;
     Queue<Integer> queue;
     /*
     List<Integer> seq;
     List<Integer> depth;
     int[] firstIndex;
     */
     int[] level;
     int[][] ancestor;

     int operations;
     int threshold;

    
    public Tree(int n, int m) // constructor
    { 
        noOfVertices = n;
        noOfQueries = m;
        adjList= new ArrayList<Node>(noOfVertices+1);
        
        for (int i = 0; i <= n; i++) // one indexing 
            adjList.add(new Node(i));
        
    }

    public void addEdge(int i, int j)
    {
        addEdgeHelper(i, j);
        addEdgeHelper(j, i);
    }
    
    private void addEdgeHelper(int from, int to) 
    {
        Node newNode = new Node(to);
        newNode.next = adjList.get(from).next;
        adjList.get(from).next = newNode;
    }
    
    
    
    public void initializeTree()
    {
        dist = new int[noOfVertices + 1];
        Arrays.fill(dist, noOfVertices); // fills with value n which is maximum in whole tree case scenario
        dist[1] = 0;

        queue = new ArrayDeque<Integer>(noOfVertices);  // Queue is an integer
        queue.offer(1); // offer = add
        bfs(); //updates distances array 

        /*
        seq = new ArrayList<>();
        depth = new ArrayList<>();
        firstIndex = new int[n + 1];
        dfs(1, 0, new boolean[n + 1]);
        */
        
        int limit =  (int)  ceil((log(noOfVertices)/log(2)));
        ancestor = new int[noOfVertices+1][limit];
        
        for (int i = 0; i <= noOfVertices; i++)
          for (int j = 0; 1 << j < noOfVertices; j++)
              ancestor[i][j] = -1;
        
        
        level = new int[noOfVertices+1];
        
        dfs(-1,1,0,new boolean[noOfVertices+1]);
   
        //bottom up dynamic programing
        for (int j = 1; 1 << j < noOfVertices; j++)
            for (int i = 0; i <= noOfVertices; i++)
                if (ancestor[i][j - 1] != -1)
                        ancestor[i][j] = ancestor[  ancestor[i][j - 1] ][j - 1];
                
        /*
        int maxK = (int) (Math.log(seq.size()) / Math.log(2));
        min = new int[seq.size()][maxK+1];
        
            
        for (int i = 0; i < seq.size(); i++)
            min[i][0] = seq.get(i);
        
        
        for (int k = 1; k <= maxK; k++)
        {
            for (int i = seq.size() - (1 << k); i >= 0; i--)
            {
                if (getDepth(min[i][k-1]) < getDepth(min[i + (1 << (k - 1))][k-1]))
                        min[i][k] = min[i][k-1];
                 else 
                    min[i][k] = min[i + (1 << (k - 1))][k-1];
                
            }
        }
        */
        
        
        threshold = (int) Math.sqrt(noOfQueries);
    }
    
    private void bfs()
    {
        while (!queue.isEmpty())
        {
            int x = queue.poll(); // remove
            
            for (Node current = adjList.get(x).next ; current != null; current = current.next)
            {
                if (dist[x] + 1 < dist[current.v])
                {
                    dist[current.v] = dist[x] + 1;
                    queue.offer(current.v);
                }
            }
        }
    }
    
    private void dfs(int prev , int root , int depth, boolean[] visited)
    {
        
        level[root] = depth; // depth of each node found by dfs . depth begins with 0.
        ancestor[root][0] = prev;
        visited[root] =true;
        
        for (Node current = adjList.get(root).next; current != null; current = current.next)
                if(!visited[current.v])
                    dfs(root , current.v, depth + 1 ,visited);
                
                
    }
    
    
    public void set(int i)
    {
        dist[i] = 0;
        queue.offer(i);
        updateOperation();
    }
    
    
    public int query(int i)
    {
        int minimum = dist[i];

        for (int v: queue)
        {
            int lca = leastCommonAncestor(i, v);
            minimum = min(minimum, level[i] + level[v] - level[lca] * 2);
        }

        updateOperation();
        return minimum;
    }

    
    private void updateOperation()
    {
        operations++;
        
        if (operations > threshold)
        {
            bfs();
            threshold += (int) sqrt(noOfQueries);
        }
    }
    
    private int leastCommonAncestor(int p, int q)
    {
        
             int tmp, log, i;
               
             //if p is situated on a higher level than q then we swap them
            if (level[p] < level[q])
            {
                tmp = p;
                p = q;
                q = tmp;
            }
              
            //we compute the value of [log(L[p)]
            for (log = 1; 1 << log <= level[p]; log++);
                  log--;
               
            //we find the ancestor of node p situated on the same level
            //with q using the values in P
            for (i = log; i >= 0; i--)
              if (level[p] - (1 << i) >= level[q])
                  p = ancestor[p][i];
               
            if (p == q)
              return p;
       
            //we compute LCA(p, q) using the values in P
            for (i = log; i >= 0; i--)
                if (ancestor[p][i] != -1 && ancestor[p][i] != ancestor[q][i])
                {
                    p = ancestor[p][i];
                    q = ancestor[q][i];
                }
               
            return ancestor[p][0];
                    
        
    }
    
        
}
