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.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Vector;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.Writer;
import java.io.InputStream;




 
 
 
 
public class seventh {
	public static void main(String[] args) {
	InputReader in=new InputReader(System.in);
	OutputWriter out=new OutputWriter(System.out);
		Task solver = new Task();
		int t=1;
		solver.solve(t, in, out);
		out.close();
	}
}
 
class Task {
 
    
	
	
	static Vector<Integer> vi[];
 static int len[];
    static int edges[][];
    static boolean b[][];
    static int which[][];
    static int L;
    static int W;
    static int par[];
    static int  parent[];
    
    static int[] sz;
    static int[] color;
    static int[] vertices;
    static int[] depth;
    static int[] weight;
    static int cnv;
    static int type[];
    static int ww[];
    static void dfs(int v, int p) {
        sz[v] = 1;
        for (int i = 0; i < edges[v].length; i++) {
           int  e = edges[v][i];
            if (b[v][i] || e == p) {
                continue;
            }
            dfs(e, v);
            sz[v] += sz[e];
        }
    }
 
    static void dfs2(int v, int p, int w, int d) {
        vertices[cnv++] = v;
        depth[v] = d;
        weight[v] = w;
       
        for (int i = 0; i < edges[v].length; i++) {
            int  e = edges[v][i];
             if (b[v][i] || e == p) {
                 continue;
             }
           {
            dfs2(e, v, w, d + 1);
            
            }
        }
    }
 
    static void color(int v, int p, int c) {
        color[v] = c;
     
        for (int i = 0; i < edges[v].length; i++) {
            int  e = edges[v][i];
             if (b[v][i] || e == p) {
                 continue;
             }
            color(e, v, c);
        }
    }
 
    static int  solve(int v) {
    	
    
    	
        cnv = 0;
        dfs(v, -1);
        {
            int all = sz[v];
            int p = -1;
            boolean changed = true;
            while (changed) {
                changed = false;
                for (int i = 0; i < edges[v].length; i++) {
                    int  e = edges[v][i];
                     if (b[v][i] || e == p) {
                         continue;
                     }
                    if (sz[e] * 2 > all) {
                        p = v;
                        v = e;
                        changed = true;
                        break;
                    }
                }
            }
         
        }
        
       
        dfs(v, -1);
        dfs2(v, -1, 0, 0);
    
        
        int countChildren = 0;
        for (int i = 0; i < edges[v].length; i++) {
            int  e = edges[v][i];
             if (b[v][i]) {
                 continue;
             }
            countChildren++;
        }
        int[] children = new int[countChildren];
        countChildren = 0;
        for (int i = 0; i < edges[v].length; i++) {
            int  e = edges[v][i];
             if (b[v][i]) {
                 continue;
             }
            children[countChildren++] = e;
        }
    
      
    
        
        int countColors = 0;
        
        color[v] = countColors++;
        for (int i = 0; i < edges[v].length; i++) {
            int  e = edges[v][i];
             if (b[v][i]) {
                 continue;
             }
            color(e, v, countColors++);
        }
    	
    	      
   
        for (int i = 0; i < edges[v].length; i++) {
          
            
            b[v][i]=true;
            b[edges[v][i]][which[v][i]]=true;
            
        }
        for (int i : children) {
        
       int which=     solve(i);
       vi[v].add(which);
       parent[which]=v;
        }
        return v;
    }
 
    static long answer;
static long answer1;
long maxxx[];
    public void solve(int testNumber, InputReader in, OutputWriter out) {
    	
    	while(testNumber>0){
        int n = in.readInt();
        
        
        maxxx=new long[n];
        Arrays.fill(maxxx, Integer.MAX_VALUE);
        vi=new Vector[n];
        parent=new int[n];
        Arrays.fill(parent,-1);
        for(int i=0;i<n;i++){
        	vi[i]=new Vector<Integer>();
        }
        
        edges = new int[n][];
        
        which = new int[n][];
        
        b = new boolean[n][];
     int m=in.readInt();
        ww=new int[n];
        for(int i=0;i<n;i++){
        	//ww[i]=in.readInt();
        }
        int size[]=new int[n];
        int ee[][]=new int[n-1][2];
        for (int i = 1; i < n; i++) {
            int u = in.readInt()- 1;
            int v = in.readInt()-1;
            ee[i-1][0]=u;
            ee[i-1][1]=v;
            size[u]++;
            size[v]++;
            }
        int count[]=new int[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new int[size[i]];
            b[i]=new boolean[size[i]];
            which[i]=new int[size[i]];
        }
        for (int i = 1; i < n; i++) {
         
          int u=    ee[i-1][0];
          int v=  ee[i-1][1];
//            //System.out.println(i + " " + p);
          
            edges[u][count[u]]=v;
            edges[v][count[v]]=u;
            which[u][count[u]]=count[v];
            which[v][count[v]]=count[u];
            
            count[u]++;count[v]++;
        }
        answer = 0;answer1=0;
        sz = new int[n];
        vertices = new int[n];
        color = new int[n];
        weight = new int[n];
        depth = new int[n];
        type=new int[n];
      par=new int[n];
        len=new int[n];
        
        par[0]=-1;
        dfff(0, -1);
        int tab[][]=dyanamicapproach(par, n);
 //     System.out.println(  getLCA(4, 3, tab)+" asdasdasd");
        solve(0);
        
        for (int i = 0; i < n; i++) {
        	  b[i]=new boolean[size[i]];
        }
      boolean b=true;
      
      
      
      for(int i=0;i<=3;i++){
    	  for(int j=0;j<vi[i].size();j++){
    	  //System.out.print(vi[i].get(j)+" ");
    	  
    	  }
    	 // System.out.println("sdf");
      }
      
      if(b==true){
    	  int no1=0;
  		int hehe1=no1;
  		maxxx[no1]=Math.min(maxxx[no1], 0);
  		while(parent[hehe1]!=-1){
  			maxxx[parent[hehe1]]=Math.min(maxxx[parent[hehe1]], len[no1]+len[parent[hehe1]]-2*len[getLCA(no1, parent[hehe1], tab)]);
  		hehe1=parent[hehe1];
  	
  	}
      }

        while(m>0){
        	
        	int type1=in.readInt();
        	
        	
        	if(type1==1){
        		int no=in.readInt()-1;
        		int hehe=no;
        		maxxx[no]=Math.min(maxxx[no], 0);
        		while(parent[hehe]!=-1){
        			maxxx[parent[hehe]]=Math.min(maxxx[parent[hehe]], len[no]+len[parent[hehe]]-2*len[getLCA(no, parent[hehe], tab)]);
        		hehe=parent[hehe];
        		}
        		
        	
        		
        	}
        	else{
        		int no=in.readInt()-1;
        		long ans=Integer.MAX_VALUE;
        		
        		ans=Math.min(ans, maxxx[no]);
        		int hehe=no;
        		while(parent[hehe]!=-1){
        			//System.out.println(hehe+" "+parent[hehe]+" "+maxxx[parent[hehe]]+" "+len[no]+len[parent[hehe]]+" "+2*len[getLCA(no, parent[hehe], tab)]);
        			ans=Math.min(ans, maxxx[parent[hehe]]+len[no]+len[parent[hehe]]-2*len[getLCA(no, parent[hehe], tab)]);
        		hehe=parent[hehe];
        		}
        		
        		
        		
        		System.out.println(ans);
        		
        		
        		
        		
        	}
        	
        	
        	
        	
        	m--;
        }
        
     
        //out.printLine((answer-answer1)>> 1);
        testNumber--;
      
        }
    	out.close();
    }
    
    
    
    
    static int[][] dyanamicapproach(int parent[],int root){
    	int n=root;

    	int log=0;



    	for( log=0;(1<<log)<n;log++);


    		int table[][]=new int[log+1][n];
    		
    		
    		
    		for(int i=0;i<n;i++)table[0][i]=parent[i];
    		
    		for(int j=1;j<=log;j++){
    			
    			for(int i=0;i<n;i++){
    				table[j][i]=-1;
    				
    				table[j][i]=table[j-1][i]==-1?-1:table[j-1][table[j-1][i]];
    				
    				
    			}
    		}
    		
    		
    		
    		return table;
    		
    	}

    	public static  int getLCA(int p, int q,int[][]total) {
    		int P[][]=total;
    	    if (len[p] < len[q]) {
    	        int tmp = p;
    	        p = q;
    	        q = tmp;
    	    }
    	    int log;
    	    for (log = 1; 1 << log <= len[p]; log++)
    	        ;
    	    log--;
    	    for (int i = log; i >= 0; i--) {
    	        if (len[p] - (1 << i) >= len[q])
    	            p = P[i][p];
    	    }
    	    if (p == q)
    	        return p;
    	    for (int i = log; i >= 0; i--) {
    	        if (P[i][p] != -1 && P[i][p] != P[i][q]) {
    	            p = P[i][p];
    	            q = P[i][q];
    	        }
    	    }
    	    return par[p];
    	}



    	static int ancestor (int table[][],int depth,int child){
    		
    		int m=depth;
    		
    		int parent=child;
    		int i=0;
    		for( m=depth;m>0;m=m>>>1){
    			if(parent==-1){
    				break;
    			}
    			if((m&1)==1){
    				parent=table[i][parent];
    			}
    			
    			i++;
    		}
    		/*
    		int a=child;
    		int m=depth;
    		
    			for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
    				if ((m & 1) == 1)
    					a = table[i][a];
    			}
    			return a;
    		*/
    		return parent;
    		
    	}
    
    void dfff(int so,int pare){
    	
    	for(int i=0;i<edges[so].length;i++){
    		if(edges[so][i]==pare){
    			
    		}
    		else{
    			par[edges[so][i]]=so;
    			len[edges[so][i]]=len[so]+1;
    			dfff(edges[so][i], so);
    		}
    	}
    	
    	
    	
    }
}
 

class InputReader {
	 
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		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 int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	public void flush() {
		writer.flush();
	}

	}

class IOUtils {

	public static int[] readIntArray(InputReader in, int size) {
		int[] array = new int[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readInt();
		return array;
	}

	}