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.*;

public class CFA {

  static final PrintWriter out = new PrintWriter(System.out);
  static final Scanner in = new Scanner(System.in);

  static void printLine(int s) {
    System.out.println(s);
  }

  static void pr(String s) {
    System.out.println(s);
  }

  public static void main(final String[] args) throws Exception {
    new CFA().main();
    out.close();
  }

  int n, m, root;
  Set<Integer> adj[];
  int parent[], subtree_size[], nodeColor[];
  int redDist[];

  int[][] anc;
  int[] depth;

  void takeInput(){
    n = in.nextInt();
    m = in.nextInt();

    parent = new int[n];
    depth = new int[n];
    redDist = new int[n];
    subtree_size = new int[n];
    adj = new HashSet[n];

    for(int i = 0;i < n;i++) adj[i] = new HashSet<>();

    for(int i = 0;i < n-1;i++){
      int a = in.nextInt() - 1;
      int b = in.nextInt() - 1;
      adj[a].add(b);
      adj[b].add(a);
    }

    Arrays.fill(parent, -1);

    Arrays.fill(redDist, Integer.MAX_VALUE);   
  }

  //########## LCA code starts here #############//
  void setParent(int node, int par, int d){
    parent[node] = par;
    depth[node] = d;

    for(int u : adj[node])
      if(u != par)
        setParent(u, node, d+1);
    
  }

  void preprocess(){
    //..considering node "0" as root run a dfs to set parent of every node
    setParent(0,-1,0); 

    anc = new int[n][log(n)+1];
    for(int i = 0;i < n;i++)
      Arrays.fill(anc[i], -1);    

    for(int i = 0;i < n;i++)
      anc[i][0] = parent[i];
    
    for(int j = 1;j <= log(n);j++)
      for(int i = 0;i < n;i++)
        if(anc[i][j-1] != -1)
          anc[i][j] = anc[anc[i][j-1]][j-1];      

  }

  //..calculates distance between two nodes "a" and "b"
  int dist(int a, int b){
    int lca = LCA(a,b);
    return depth[a] + depth[b] - (2*depth[lca]);
  }

  int LCA(int a, int b){

    if(depth[a] < depth[b]){
      int temp = a;
      a = b;
      b = temp;
    }

    int diff = depth[a] - depth[b];
    while(diff > 0){
      int i = log(diff);
      a = anc[a][i];
      diff -= (1 << i);
    }
    
    if(a == b)
      return a;

    for(int i = log(n);i >= 0;i--)
      if(anc[a][i] != -1 && anc[a][i] != anc[b][i]){
        a = anc[a][i];
        b = anc[b][i];
      }
    

    //..don't return parent[a] because after decomposition
    //..parent[] array is according to centroid tree
    return anc[a][0]; 
  }

  //###################### LCA code ends here ####################//

  int log(int x){
    return (int)(Math.log(x)/Math.log(2));
  }

  
  int subtree_size_dfs(int u, int par){
    int count = 1; 

    for(int child : adj[u]){
        if(child == par) continue;
        count += subtree_size_dfs(child, u);
    }

    subtree_size[u] = count; 
    return count;
  }  

  int findCentroid(int node , int par , int n){        
    for(int neighbour : adj[node]){ 
        if(neighbour == par) continue;
            
        if(subtree_size[neighbour] > n/2)
          return findCentroid(neighbour , node , n);
    }        
    
    return node;
  }

  void decompose(int node , int oldCentroid){
    int subTreeSize = subtree_size_dfs(node, -1);
    int centroid = findCentroid(node , oldCentroid , subTreeSize);

    parent[centroid] = oldCentroid;                         
    
    for(int neighbour : adj[centroid]){
      adj[neighbour].remove(centroid);
      decompose(neighbour , centroid);
    }
  }

  void paintNode(int u){
    int centroid = u;

    //..climb up the centroid tree and notify all the parent centroids
    //..if redDist is less then store it.
    while(centroid != -1){      
      redDist[centroid] = Math.min(redDist[centroid], dist(u, centroid));
      centroid = parent[centroid];
    }
}


  void printMinDist(int u){
  
    long min = Integer.MAX_VALUE;
    int centroid = u;

    //..find the centroid who is closest to both nodes
    while(centroid != -1){   
      min = Math.min((long)redDist[centroid] + dist(u, centroid), min);
      centroid = parent[centroid];
    }

    printLine((int)min);    
  }

  void main(){
    takeInput(); //..store the tree in adjacency set
    preprocess(); //..for binary lifting
    decompose(0, -1); //..centroid decomposition
    paintNode(0); //..paintNode "0"

    for(int i = 0;i < m;i++){ 
      int query_type = in.nextInt();
      int node = in.nextInt() - 1;
    
      if(query_type == 1)
        paintNode(node);
      else
        printMinDist(node);  
    }
  }

}

/**
10 1
10 7
10 6
1 4
7 8
5 1
6 2
7 5
6 3
7 9

 */
