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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class E199 implements Runnable{
	static final int oo = 1000000000;
	static int[] dist;
	static boolean[] red;
	static ArrayList<Integer>[] adj;
	public static void main(String[] args) throws FileNotFoundException {
		new Thread(null, new E199(), "cool", 1<<28).start();
	}
	
	public void run() {
		FS scan= new FS(System.in);
		PrintWriter out=new PrintWriter(System.out);
//		try {
//			scan = new FS(new FileInputStream(new File("test.in")));
//			out = new PrintWriter(new File("sol.out"));
//		} catch (FileNotFoundException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
		int N = scan.nextInt(), Q = scan.nextInt();
		
		adj = new ArrayList[N];
		for(int i=0;i<N;i++)adj[i] = new ArrayList<>();
		
		red = new boolean[N];
		dist = new int[N];
		Arrays.fill(dist, oo);
		dist[0] = 0;
		red[0] = true;
		
		for(int i=0;i<N-1;i++){
			int u = scan.nextInt()-1, v = scan.nextInt()-1;
			adj[u].add(v);
			adj[v].add(u);
		}
		int[][] ADJ = new int[N][];
		for(int i=0;i<N;i++){
			ADJ[i] = new int[adj[i].size()];
			for(int j=0;j<adj[i].size();j++)
				ADJ[i][j] = adj[i].get(j);
		}
		int[] t = new int[Q];
		int[] v = new int[Q];
		for(int i=0;i<Q;i++){
			t[i] = scan.nextInt();
			v[i] = scan.nextInt()-1;
		}
		
		LCAFast lca = new LCAFast(adj);
		ArrayList<Integer> cur = null;
		int sqrt = (int)Math.sqrt(Q);
		for(int i=0;i<Q;i++){
			if(i%sqrt==0){
				cur = new ArrayList<>();
				for(int j=i;j<i+sqrt && j<Q; j++){
					if(t[j]==2)cur.add(v[j]);
				}
				updateDist(ADJ);
			}
			if(t[i]==2){
				out.println(dist[v[i]]);
			}else{
				red[v[i]]=true;
				dist[v[i]]=0;
				for(int j : cur){
					dist[j] = Math.min(dist[j], lca.dist(j, v[i]));
				}
			}
		}
		out.close();
	}
	private static void updateDist( int[][] g ) {
		
		int N = red.length;
		ArrayDeque<Integer> q = new ArrayDeque<>();
		for(int i=0;i<N;i++){
			if(red[i]){
				q.add(i);
				dist[i] = 0;
			}else{
				dist[i]=oo;
			}
		}
		while(!q.isEmpty()){
			int node = q.poll();
			for(int i : g[node]) {
				if(dist[i]==oo){
					dist[i] = dist[node]+1;
					q.add(i);
				}
			}
		}
	}
	

	private static class LCAFast {
		
		static ArrayList<Integer> ord, h;
		static int[] first;
		static RMQ rmq;
		public LCAFast(ArrayList<Integer>[] adj) {
			ord = new ArrayList<>();
			h = new ArrayList<>();
			first = new int[adj.length];
			dfs(adj,0,-1,0);
			int[] tH = new int[h.size()];
			for(int i=0;i<tH.length;i++)tH[i] = h.get(i);
			rmq = new RMQ(tH);
		}
		private void dfs(ArrayList<Integer>[] adj, int idx, int par, int h) {
			first[idx] = ord.size();
			ord.add(idx);
			this.h.add(h);
			for(int i : adj[idx]){
				if(i==par)continue;
				dfs(adj,i,idx,h+1);
				ord.add(idx);
				this.h.add(h);
			}
		}
		private int lca(int u, int v) {
			return ord.get(rmq.min(first[u],first[v]));
		}
		private int dist (int u, int v) {
			int lca = lca(u,v);
			return h.get(first[u])+h.get(first[v])-2*h.get(first[lca]);
		}
	}
	private static class RMQ {
		int[] input;
		int logmax, N;
		int[][] rMinQ;
		public RMQ(int[] input) {
			N = input.length;
			this.input = input;
			logmax = (int)Math.ceil(Math.log(N)/Math.log(2.));
			rMinQ = new int[logmax+1][N];	
			for(int i=0;i<N;i++){rMinQ[0][i]=i;}
			for(int j=1; 1<<j <= N; j++){
				for (int i=0; i + (1<<j)-1 < N; i++){
					//<= and >= gives first occurance :: < and > gives last
					if (input[rMinQ[j-1][i]] <= input[rMinQ[j-1][i+(1<<(j-1))]])rMinQ[j][i]=rMinQ[j-1][i];
					else rMinQ[j][i] = rMinQ[j-1][i+(1<<(j-1))];
				}
			}
		}
		private int min(int i, int j){
			if(i>j)
				i = i^j^(j=i);
			int k = (int)(Math.log(j-i+1)/Math.log(2.0));
			if(input[rMinQ[k][i]] <= input[rMinQ[k][j-(1<<k)+1]])return rMinQ[k][i];
			else return rMinQ[k][j-(1<<k)+1];
		}
	}
	private static class FS {
		BufferedReader br;
		StringTokenizer st;
		public FS(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() { return Double.parseDouble(next());}
	}
}
