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 AA {
	static PrintWriter pw;
	public static void main(String[] args)throws Throwable {
		pw=new PrintWriter(System.out);
		MyScanner sc=new MyScanner();
		
		n=sc.nextInt();
		int m=sc.nextInt();
		adj=new ArrayList [n];
		for(int i=0;i<n;i++)
			adj[i]=new ArrayList<Integer>();
		for(int i=0;i<n-1;i++){
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			adj[u].add(v);
			adj[v].add(u);
		}
		preProcessing();
		int [] dis=new int [n];
		for(int i=0;i<n;i++)
			dis[i]=level[i];
		ArrayList<Integer> arr=new ArrayList<Integer>();
		int c=0;
		int [] vis=new int [n];
		int vid=0;
		while(m-->0){
			int t=sc.nextInt();
			int x=sc.nextInt()-1;
			if(t==1){
				arr.add(x);
				c++;				
			}
			else{
				int ans=dis[x];
				for(int y : arr)
					ans=Math.min(ans, level[x]+level[y]-2*level[query(x, y)]);
				pw.println(ans);
			}
			if(c==200){
				vid++;
				int [] q=new int [n+5];
				int f=0,e=0;
				for(int y : arr){
					dis[y]=0;
					vis[y]=vid;
					q[e++]=y;
				}
				while(f!=e){
					int u=q[f++];
					for(int v : adj[u])
						if(vis[v]!=vid && dis[v]>dis[u]+1){
							vis[v]=vid;
							dis[v]=dis[u]+1;
							q[e++]=v;
						}
				}
				arr.clear();
				c=0;
			}
		}
		
		
		pw.flush();
		pw.close();
	}
	
	static int n;
	static int [][] ansector;
	static int [] parent,level;
	static ArrayList<Integer> [] adj;
	
	static void preProcessing(){
		parent=new int [n];
		level=new int [n];
		parent[0]=-1;
		dfs(0, 0);
		int log=(int)Math.ceil(Math.log(n)/Math.log(2));
		ansector=new int [n][log];
		for(int [] x : ansector)
			Arrays.fill(x, -1);
		for(int i=0;i<n;i++)
			ansector[i][0]=parent[i];				
		for(int j=1;(1<<j)<n;j++)
			for(int i=0;i<n;i++)
				if(ansector[i][j-1]!=-1)
					ansector[i][j]=ansector[ansector[i][j-1]][j-1];
	}
	
	public static void dfs(int u,int h){
		level[u]=h;
		for(int v : adj[u])
			if(v!=parent[u]){
				parent[v]=u;
				dfs(v, h+1);
			}
	}
	
	public static int query(int u,int v){
		if(level[u]<level[v]){
			int tmp=u;
			u=v;
			v=tmp;
		}
		int log=1;
		for(log=1;(1<<log)<=level[u];log++);
		log--;
		
		for(int i=log;i>=0;i--)
			if(level[u]-(1<<i)>=level[v])
				u=ansector[u][i];
		
		if(u==v)
			return u;
		
		for(int i=log;i>=0;i--)
			if(ansector[u][i]!=-1 && ansector[u][i]!=ansector[v][i]){
				u=ansector[u][i];
				v=ansector[v][i];
			}
		return parent[u];
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.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());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
}