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
/* Nice question : 
 I solved it using editorial Approach

This can also be solved with centroid decomposition in nlog(n) . I will solve this when I will lean C.D

*/
import java.util.*;
import java.io.*;
import java.math.BigInteger; 
public class lp1{ 
static PrintWriter out = new PrintWriter(System.out);
static int lg=0;
static void log(int n)
{
     int c=1;
     while(c<n)
     {
       c=c*2;
       lg++;
     }
       lg++;
}      
static void dfs(LinkedList<Integer> l[],int s,int p,int level[],int dp[][],int dist[])
{
          dp[s][0]=p;
       for(Integer i: l[s])
          if(i!=p)
           {
              level[i]=level[s]+1;
              dist[i]= level[i];
              dfs(l,i,s,level,dp,dist);
           }
}
static void precalculate(int dp[][])
{
          int N = dp.length;
           for(int h = 1; h < lg; h++)
              for(int i = 0; i < N; i++)
                  if(dp[i][h-1] != -1)
                     dp[i][h] = dp[dp[i][h-1]][h-1];
                  else
                     dp[i][h]=-1;
}
static int lca(int a,int b,int level[],int dp[][])
{
	if(level[a]<level[b])
           return lca(b,a,level,dp);
        int lg1=0;
	for(lg1 =0 ; (1<<lg1) <= level[a]; lg1++);
	
	for(int i = lg1 - 1; i >= 0; i--)
	   if((level[a] - (1<<i)) >= level[b])
			a = dp[a][i];
	
	  if(a == b)
	        return a;
	  for(int i = lg1; i >= 0; i--)
		if(dp[a][i] != dp[b][i]){
			a = dp[a][i];
			b = dp[b][i];
		}
	    return dp[a][0]; 
}


static void solve() {

int n = ni();
int m = ni();
 log(n);
int level[] = new int[n];
int dp[][] = new int[n][lg];
int col[] = new int[n];
int dist[] = new int[n];
LinkedList<Integer> l[] = new LinkedList[n];

for(int i=0;i<n;i++)
    l[i] = new LinkedList();

for(int i=1;i<n;i++)
{
   int u = ni()-1;
   int v = ni()-1;
   l[u].add(v);
   l[v].add(u);
}
 dfs(l,0,-1,level,dp,dist);
 precalculate(dp);
int ct=0;
ArrayList<Integer> arr = new ArrayList();
for(int yu=1;yu<=m;yu++)
{
    int t = ni();
    int v = ni()-1;
    if(t==1){
       dist[v]=0;      
       arr.add(v);
       ct++;
    }
  else{
       int ans = dist[v];
       if(ans==0) {pn(0); continue;}
       else{
             for(Integer I : arr)
              ans = Math.min(ans,level[I]+level[v] -2*level[lca(I,v,level,dp)]);
                pn(ans);
       }
   }
 if(ct==200)
  {
       LinkedList<Integer> queue = new LinkedList();
       boolean vis[] = new boolean[n];
       for(Integer I : arr)
          { queue.add(I);vis[I]=true;}
       while(queue.size()>0)
         {
             int s = queue.poll();
             for(Integer I : l[s])
                 if(vis[I]==false&&dist[I]>(dist[s]+1))
                     { vis[I]=true; dist[I] = dist[s]+1;queue.add(I);}
          }
       ct=0;
       arr.clear();
   }
}
   out.flush();
}
public static void main(String[] args) throws Exception{

solve();

/* use this block when you need more recursion depth
new Thread(null, null, "Name", 999) {
            public void run() {
                try {
                    solve();
                } catch(Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();   */
} 
static int[] ai(int n)  // it will give in array of size n
{
    int a[] = new int[n];
    for(int i=0;i<n;i++)
        a[i] = ni();
    return a;
}
static long[] al(int n)  // it will give in array of size n
{
    long a[] = new long[n];
    for(int i=0;i<n;i++)
        a[i] = nl();
    return a;
}
 
static void p(Object o)
{
   out.print(o);
}
static void pn(Object o)
{
    out.println(o);
}
static int abs(int x)
{
    return x>0 ? x : -x;
}
static long gcd(long a,long b)
{
       if(a==0)
          return b;
       if(b==0)
          return a;
       if(b%a==0)
          return a;
          return gcd(b%a,a);
}
static int count_set(int n)
{
   int c=0;
while(n>0)
{
   if(n%2==1)
     c++;
     n=n/2;
}
   return c;
}
static void subtract_1(char s[]) // it will subtract 1 from the given number.  number should be positive
{
      if(s[0]=='0') // number is zero
          return;
     int n = s.length,i=n-1;
     while(s[i]=='0')
       i--;
     s[i] = (char)((int)(s[i]-'0') + 47);
   
     for(int j=i+1;j<n;j++)
         s[j]='9';
}
static long pow(long a,long b,long md)
{ 
    long ans=1;
    while(b>0)
    {
         if(b%2==1)
           ans = (ans*a)%md;
           a = (a*a)%md;
           b = b/2;
    }
   return ans;
}
static long min(long a,long b){
 
     return a<b ? a : b;
}
static long max(long a,long b){
     return a>b ? a : b;
}
static boolean pal(String s)
{
   int n = s.length(),i1=0,i2=n-1;
 
     while(i1<i2)
     {
        if(s.charAt(i1)!=s.charAt(i2))
             return false;
             i1++; i2--;
     }
       return true;
}
static String rev(String r)
{
    String s = "";
    int i= r.length()-1;
 
    while(i>=0)
    {
        s=s+r.charAt(i);
        i--;   
    }
       return s;
}
static FastReader sc=new FastReader(); 
 
      static int ni(){
                 int x = sc.nextInt();
                 return(x);
        }
      static long nl(){
              long x = sc.nextLong();
              return(x);
         }
      static String n(){
                 String str = sc.next();
                     return(str);
       }
     static String ns(){
                 String str = sc.nextLine();
                   return(str);
      }
     static double nd(){
               double d = sc.nextDouble();
                 return(d);
       }
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            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; 
        } 
    } 
}