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 final class xenia_and_tree
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static int[][] al;
	static int[] dis,parent,count,size;
	static int ctr;
	static boolean[] removed;
	static int[] tin,tout,level,parent1;
	static int time=-1,LN=21;
	static int[][] st;
	
	static void build(int u,int p)
	{
		ctr++;size[u]=1;
		for(int x:al[u])
		{
			if(x!=p && !removed[x])
			{
				build(x,u);size[u]+=size[x];
			}
		}
	}
	
	static void dfs(int u,int p,int curr)
	{
		tin[u]=++time;level[u]=curr;parent1[u]=p;
		for(int x:al[u])
		{
			if(x!=p)
			{
				dfs(x,u,curr+1);
			}
		}
		tout[u]=time;
	}
	
	static int lca(int u,int v)
	{
		if(isAncestor(u,v))
			return u;
		if(isAncestor(v,u))
			return v;
		for(int i=LN-1;i>=0;i--)
		{
			if(!isAncestor(st[i][u],v))
			{
				u=st[i][u];
			}
		}
		return st[0][u];
	}
	
	static boolean isAncestor(int u,int v)
	{
		return (tin[u]<=tin[v] && tout[u]>=tout[v]);
	}
	
	static int findCentroid(int u,int p)
	{
		int max=-1,big_child=-1;
		for(int x:al[u])
		{
			if(x!=p && !removed[x] && size[x]>max)
			{
				max=size[x];big_child=x;
			}
		}
		if(max<=ctr/2 && ctr-size[u]<=ctr/2)
		{
			return u;
		}
		return findCentroid(big_child,u);
	}
	
	static int dis(int u,int v)
	{
		if(isAncestor(u,v))
			return level[v]-level[u];
		if(isAncestor(v,u))
			return level[u]-level[v];
		return level[u]+level[v]-(level[lca(u,v)]<<1);
	}
	
	static void decompose(int u,int p)
	{
		ctr=0;build(u,p);int centroid=findCentroid(u,p);removed[centroid]=true;parent[centroid]=p;
		for(int x:al[centroid])
		{
			if(x!=p && !removed[x])
			{
				decompose(x,centroid);
			}
		}
	}
	
	@SuppressWarnings("unchecked")
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt(),m=sc.nextInt();List<Node> list=new ArrayList<Node>();count=new int[n];
		for(int i=1;i<n;i++)
		{
			int u=sc.nextInt()-1,v=sc.nextInt()-1;list.add(new Node(u,v));count[u]++;count[v]++;
		}
		al=new int[n][];
		for(int i=0;i<n;i++)
		{
			al[i]=new int[count[i]];
		}
		count=new int[n];
		for(int i=0;i<list.size();i++)
		{
			int u=list.get(i).u,v=list.get(i).v;
			al[u][count[u]]=v;al[v][count[v]]=u;
			count[u]++;count[v]++;
		}
		tin=new int[n];tout=new int[n];level=new int[n];parent1=new int[n];dfs(0,0,1);st=new int[LN][n+2];
		for(int i=0;i<n;i++)
		{
			st[0][i]=parent1[i];
		}
		for(int i=1;i<LN;i++)
		{
			for(int j=0;j<n;j++)
			{
				st[i][j]=st[i-1][st[i-1][j]];
			}
		}
		size=new int[n];removed=new boolean[n];parent=new int[n];decompose(0,-1);dis=new int[n];Arrays.fill(dis,Integer.MAX_VALUE);int curr=0;
		while(curr!=-1)
		{
			dis[curr]=dis(curr,0);curr=parent[curr];
		}
		while(m>0)
		{
			int t=sc.nextInt();
			if(t==1)
			{
				int u=sc.nextInt()-1,v=u;
				while(v!=-1)
				{
					dis[v]=Math.min(dis[v],dis(u,v));v=parent[v];
				}
			}
			else
			{
				int u=sc.nextInt()-1,v=u,ans=Integer.MAX_VALUE;
				while(v!=-1)
				{
					if(dis[v]<Integer.MAX_VALUE)
					{
						ans=Math.min(ans,dis(u,v)+dis[v]);
					}
					v=parent[v];
				}
				out.println(ans);
			}
			m--;
		}
		out.close();
    }
}
class Node
{
	int u,v;
	public Node(int u,int v)
	{
		this.u=u;this.v=v;
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}