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 ladder{

	static int LG=20;
	static int [][]up;
	static int []level;
	static void pre(int u,int p)
	{
		up[0][u]=p;
		for(int l=1;l<LG;l++)
		{
			int x=up[l-1][up[l-1][u]];
			up[l][u]=x;
		}
		for(edge nxt:adj[u])
		{
			int v=nxt.v;
			if(level[v]==0)
			{
				level[v]=level[u]+1;
				pre(v,u);
			}
		}
	}
	static int lca(int u,int v) {
		if(level[v]>level[u]) {
			int tmp=u;
			u=v;
			v=tmp;
		}
		for(int l=LG-1;l>=0;l--)
		{
			int x=up[l][u];
			if(level[x]>=level[v])
				u=x;
		}
		if(u==v)
			return u;
		for(int l=LG-1;l>=0;l--)
		{
			int x1=up[l][u],x2=up[l][v];
			if(x1!=x2) {
				u=x1;
				v=x2;
			}
			
		}
		return up[0][u];
	}
	static int dist(int u,int v) {
		return level[u]+level[v]-2*level[lca(u,v)];
	}
	static class edge
	{
		int v;
		boolean deleted;
		edge(int a) {
			v=a;
		}
		void delete(){
			deleted=true;
		}
		boolean deleted() {
			return deleted;
		}
	}
	static ArrayList<edge>[]adj;
	
	static int cnt;
	static int []sub,par;
	static void dfs1(int u,int p)
	{
		sub[u]=1;
		cnt++;
		for(edge nxt:adj[u])
		{
			int v=nxt.v;
			if(!nxt.deleted && v!=p)
			{
				dfs1(v,u);
				sub[u]+=sub[v];
			}
		}
	}
	static int dfs2(int u,int p)
	{
		for(edge nxt:adj[u]) {
			int v=nxt.v;
			if(!nxt.deleted && v!=p && sub[v]>cnt/2)
				return dfs2(v,u);
		}
		return u;
	}
	static void decompose(int root,int p)
	{
		cnt=0;
		dfs1(root,root);
		int centroid = dfs2(root,root);
		
		if(p==-1)p=centroid;
		par[centroid]=p;
		for(edge nxt:adj[centroid] )
		{
			if(nxt.deleted)
				continue;
			boolean ok=false;
			for(edge rev:adj[nxt.v])
				if(rev.v==centroid && !rev.deleted) {
					
					rev.deleted=true;
					ok=true;
					break;
				}
			if(ok)
				decompose(nxt.v, centroid);
		}
		adj[centroid].clear();
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		int n=sc.nextInt(),m=sc.nextInt();
		adj=new ArrayList[n];
		for(int i=0;i<n;i++)
			adj[i]=new ArrayList();
		level=new int [n];
		level[0]=1;
		
		up=new int [LG][n];
		
		
		par=new int [n];
		sub=new int [n];
		for(int i=1;i<n;i++) {
			int u=sc.nextInt()-1,v=sc.nextInt()-1;
			adj[u].add(new edge(v));
			adj[v].add(new edge(u));
		}
		pre(0,0);
		
		decompose(0,-1);
		int []min=new int [n];
		for(int i=0;i<n;i++)
			min[i]=level[i]-1;
		
		while(m-->0)
		{
			int t=sc.nextInt(),u=sc.nextInt()-1;
		
			if(t==1) //update
			{
				min[u]=0;
				int v=u;
				while(v!=par[v])
				{
					v=par[v];
					min[v]=Math.min(min[v], dist(u,v));
				}
				
				
			}
			else //query
			{
				int ans=min[u];
				int v=u;
				while(v!=par[v])
				{
					v=par[v];
					ans=Math.min(ans, dist(u,v)+min[v]);
				}
				out.println(ans);
			}
		}
		
		out.close();

	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}
