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
/**
 * @author sakt_coder
 * created on 2020-10-20 16:55
 */
import java.io.*;
import java.util.*;
public class Main
{
	Graph g;
	private void solve()throws Exception
	{
		int n=nextInt();
		int m=nextInt();
		CentroidDecomposition cd=new CentroidDecomposition(n);
		g=new Graph(n);
		for(int i=1;i<n;i++)
		{
			int u=nextInt();
			int v=nextInt();
			cd.addEdge(u,v);
			g.addEdge(u,v);
		}
		cd.init();
		g.init();
		cd.update(1);
		for(int i=1;i<=m;i++)
		{
			int t=nextInt();
			if(t==1)
				cd.update(nextInt());
			else
				out.println(cd.query(nextInt()));
		}
	}
	class Graph
	{
		int n,logn,ancestor[][],depth[],start[],end[];
		ArrayList<Integer> list[],eulerList;
		Graph(int n)
		{
			this.n=n;
			list=new ArrayList[n+1];
			for(int i=1;i<=n;i++)
				list[i]=new ArrayList<>();
		}
		void addEdge(int u,int v)
		{
			list[u].add(v);
			list[v].add(u);
		}
		void init()
		{
			init(false);
		}
		void init(boolean returns)
		{
			logn=(int)Math.ceil(Math.log(n)/Math.log(2));
			ancestor=new int[n+1][logn+1];
			depth=new int[n+1];
			depth[0]=-1;
			start=new int[n+1];
			end=new int[n+1];
			eulerList=new ArrayList<>();
			eulerList.add(0);
			dfs(1,0,returns);
			for(int j=1;j<=logn;j++)
				for(int i=1;i<=n;i++)
					ancestor[i][j]=ancestor[ancestor[i][j-1]][j-1];
		}
		void dfs(int v,int p,boolean returns)
		{
			eulerList.add(v);
			start[v]=eulerList.size()-1;
			depth[v]=depth[p]+1;
			ancestor[v][0]=p;
			for(int vv:list[v])
				if(vv!=p)
					dfs(vv,v,returns);
			if(returns)
				eulerList.add(v);
			end[v]=eulerList.size()-1;
		}
		ArrayList<Integer> getEuler()
		{
			return eulerList;
		}
		int getDiameter()
		{
			return farthest(farthest(1)[0])[1];
		}
		int[] farthest(int v)
		{
			Queue<Integer> queue=new LinkedList<>();
			queue.add(v);
			int dist[]=new int[n+1];
			Arrays.fill(dist,1<<30);
			dist[v]=0;
			int max=v;
			while(!queue.isEmpty())
			{
				int curr=queue.remove();
				for(int next:list[curr])
					if(dist[next]>dist[curr]+1)
					{
						dist[next]=dist[curr]+1;
						if(dist[next]>dist[max])
							max=next;
						queue.add(next);
					}
			}
			return new int[]{max,dist[max]};
		}
		int ancestor(int i,int j)
		{
			for(int k=logn;k>=0;k--)
				if(((j>>k)&1)==1)
					i=ancestor[i][k];
			return i;
		}
		int lca(int i,int j)
		{
			if(depth[i]>depth[j])
			{
				int temp=i;
				i=j;
				j=temp;
			}
			int d=depth[j]-depth[i];
			for(int k=20;k>=0;k--)
				if(((d>>k)&1)==1)
					j=ancestor[j][k];
			if(i==j)
				return i;
			for(int k=20;k>=0;k--)
				if(ancestor[i][k]!=ancestor[j][k])
				{
					i=ancestor[i][k];
					j=ancestor[j][k];
				}
			return ancestor[i][0];
		}
		int dist(int i,int j)
		{
			if(depth[i]>depth[j])
			{
				int temp=i;
				i=j;
				j=temp;
			}
			int d=depth[j]-depth[i];
			int ret=d;
			for(int k=logn;k>=0;k--)
				if(((d>>k)&1)==1)
					j=ancestor[j][k];
			if(i==j)
				return ret;
			for(int k=logn;k>=0;k--)
				if(ancestor[i][k]!=ancestor[j][k])
				{
					i=ancestor[i][k];
					j=ancestor[j][k];
					ret+=2*(1<<k);
				}
			ret+=2;
			return ret;
		}
	}
	class CentroidDecomposition
	{
		int n,dp[],parent[];
		int subSize[];
		ArrayList<Integer> list[];
		CentroidDecomposition(int n)
		{
			this.n=n;
			dp=new int[n+1];
			Arrays.fill(dp,1<<30);
			list=new ArrayList[n+1];
			for(int i=1;i<=n;i++)
				list[i]=new ArrayList<>();
			subSize=new int[n+1];
			parent=new int[n+1];
		}
		void addEdge(int u,int v)
		{
			list[u].add(v);
			list[v].add(u);
		}
		void init()
		{
			decompose(1,0);
		}
		void decompose(int v,int p)
		{
			dfs(v,0);
			int c=centroid(v,0,subSize[v]);
			parent[c]=p;
			for(int vv:list[c])
				list[vv].remove(new Integer(c));
			for(int vv:list[c])
				decompose(vv,c);
		}
		int centroid(int v,int p,int size)
		{
			for(int vv:list[v])
				if(vv!=p && subSize[vv]>size/2)
					return centroid(vv,v,size);
			return v;
		}
		void dfs(int v,int p)
		{
			subSize[v]=1;
			for(int vv:list[v])
				if(vv!=p)
				{
					dfs(vv,v);
					subSize[v]+=subSize[vv];
				}
		}
		void update(int v)
		{
			int curr=v;
			while(curr!=0)
			{
				dp[curr]=Math.min(dp[curr],g.dist(v,curr));
				curr=parent[curr];
			}
		}
		int query(int v)
		{
			int ans=dp[v];
			int curr=parent[v];
			while(curr!=0)
			{
				ans=Math.min(ans,g.dist(curr,v)+dp[curr]);
				curr=parent[curr];
			}
			return ans;
		}
	}

	 
	///////////////////////////////////////////////////////////

	public void run()throws Exception
	{
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		try{
			solve();

		}catch(Exception e){e.printStackTrace();}
		finally{
			br.close();
			out.close();
		}
		
	}
	public static void main(String args[])throws Exception{
		new Main().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws Exception{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws Exception{
		return br.readLine();
	}
	int nextInt()throws Exception{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws Exception{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws Exception{
		return Double.parseDouble(nextToken());
	}
}
