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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

@SuppressWarnings("unused")
public class Solution{
	
	static ArrayList<Integer>[] g;
	static int[][] par;
	static int[] dep, tin, tout;
	static int[] best;
	static int timer = 0;
	static boolean[] vis;
	static int[] cpar, sz;
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    	
    	int tt = 1;
    	outer:
    	while(tt-->0) {
    		
    		int n = fs.nextInt(), m = fs.nextInt();
    		
    		g = new ArrayList[n];
    		for(int i=0;i<n;i++) g[i] = new ArrayList<Integer>();
    		
    		for(int i=0;i<n-1;i++) {
    			int u = fs.nextInt()-1, v = fs.nextInt()-1;
    			g[u].add(v);
    			g[v].add(u);
    		}
    		
    		par = new int[n][20];
    		dep = new int[n]; tin = new int[n]; tout = new int[n]; best = new int[n];
    		best[0] = 0;
    		
    		dfs(0, -1);
    		
    		for(int i=1;i<20;i++) {
    			for(int v=0;v<n;v++) {
    				if(par[v][i-1]==-1) par[v][i] = -1;
    				else par[v][i] = par[par[v][i-1]][i-1];
    			}
    		}
    		
    		vis = new boolean[n];
    		cpar = new int[n]; sz = new int[n];
    		
    		
    		decompose(0, -1);
    		
    		while(m-->0) {
    			int t = fs.nextInt(), v = fs.nextInt()-1;
    			if(t==1) {
    				int x = v;
    				while(x!=-1) {
    					best[x] = Math.min(best[x], dist(x, v));
    					x = cpar[x];
    				}
    			}
    			else {
    				int x = v;
    				int ans = best[x];
    				while(x!=-1) {
    					ans = Math.min(ans, best[x] + dist(x, v));
    					x = cpar[x];
    				}
    				out.println(ans);
    			}
    		}
    		
    	}
    	
    	out.close();
    }
	
	
	
	
	static void dfs(int v, int p) {
		tin[v] = timer++;
		par[v][0] = p;
		for(int u: g[v]) {
			if(u==p) continue;
			dep[u] = dep[v] + 1;
			best[u] = best[v] + 1;
			dfs(u, v);
		}
		tout[v] = timer++;
	}
	
	static boolean isAnc(int x, int y) {
		if(x==-1) return true;
		return tin[x]<=tin[y] && tout[y]<=tout[x];
	}
	
	static int lca(int x, int y) {
		if(isAnc(x, y)) return x;
		for(int i=19;i>=0;i--) {
			if(!isAnc(par[x][i], y)) x = par[x][i];
		}
		return par[x][0];
	}
	
	static int dist(int x, int y) {
		return dep[x] + dep[y] - 2*dep[lca(x, y)];
	}
	
	
	static void find_size(int v, int p) {
		sz[v] = 1;
		for(int u: g[v]) {
			if(!vis[u] && u!=p) {
				find_size(u, v);
				sz[v] += sz[u];
			}
		}
	}
	
	static int find_centroid(int v, int p, int n) {
		for(int u: g[v]) {
			if(!vis[u] && u!=p && sz[u]>n/2) return find_centroid(u, v, n);
		}
		return v;
	}
	
	
	static void decompose(int v, int p) {
		find_size(v, -1);
		int c = find_centroid(v, -1, sz[v]);
		vis[c] = true;
		cpar[c] = p;
		for(int u: g[c]) {
			if(!vis[u]) {
				decompose(u, c);
			}
		}
	}
	
	
    static final Random random=new Random();
    
    static <T> void shuffle(T[] arr) {
    	int n = arr.length;
    	for(int i=0;i<n;i++	) {
    		int k = random.nextInt(n);
    		T temp = arr[k]; arr[k] = arr[i]; arr[i] = temp;
    	}
    }
    
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
    
    static void ruffleSort(long[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); long temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    static void reverse(int[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		int temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    static void reverse(long[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		long temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    
    static <T> void reverse(T[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++) {
    		T temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }


   	
}
