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
// package Centroid_Decompsition;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class Xenia_And_Tree {
	static FastReader scn = new FastReader();
	static OutputStream out = new BufferedOutputStream(System.out);
	static HashSet<Integer> tree[];
	static int level[],dp[][],n,m,subtree_size[],ans[],INF=(int)1e9,par[];
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		n = scn.nextInt();m=scn.nextInt();
		tree=new HashSet[n+1];
		level = new int[n+1];dp = new int[log(n)+1][n+1];subtree_size=new int[n+1];ans=new int[n+1];par = new int[n+1];
		Arrays.fill(ans, INF);
		for(int i=1;i<=n;i++) {
			tree[i]=new HashSet<>();
		}
		for(int i=0;i<n-1;i++) {
			int u = scn.nextInt(),v = scn.nextInt();
			tree[u].add(v);
			tree[v].add(u);
		}
		level[0]=0;
		dp[0][0]=0;
		dfs0(1,0);
		ancestor_fill();
		decompose(1,0);
		update(1);
		
		for(int i=0;i<m;i++) {
			int t= scn.nextInt(),v= scn.nextInt();
			if(t==1) {
				update(v);
			}else {
				out.write((query(v)+"\n").getBytes());
			}
		}
		out.close();
	}
	
	/*				Handling Queries					*/
	static void update(int a) {
		int x =a;
		while(true) {
			ans[x]=Math.min(dist(x,a), ans[x]);
			if(par[x]==x)break;
			x=par[x];
		}
	}
	static int query(int a) {
		int x = a;
		int ret = INF;
		while(true) {
			ret = Math.min(dist(x,a)+ans[x], ret);
			if(par[x]==x)break;
			x=par[x];
		}
		return ret;
	}
	
	/*				Centroid Decomposition				*/
	static int nn;
	static void decompose(int root, int p) {
		nn=0;
		dfs1(root,p);
		int centroid = dfs2(root,p);
		if(p==0)p=centroid;
		par[centroid]=p;
		for(int b: tree[centroid]) {
			tree[b].remove(centroid);
			decompose(b,centroid);
		}
		tree[centroid].clear();
	}
	static void dfs1(int a, int par) {
		subtree_size[a]=1;nn++;
		for(int b:tree[a]) {
			if(par!=b) {
				dfs1(b,a);
				subtree_size[a]+=subtree_size[b];
			}
		}
	}
	static int dfs2(int a,int par) {
		for(int b:tree[a]) {
			if(par!=b&&subtree_size[b]>nn/2) {
				return dfs2(b,a);
			}
		}
		return a;
	}
	
	
	/*        LCA Parts               */
	static void dfs0(int a, int par) {
		level[a]=level[par]+1;
		dp[0][a]=par;
		for(int b:tree[a]) {
			if(b!=par) {
				dfs0(b,a);
			}
		}
	}
	static void ancestor_fill() {
		for(int i=1;i<dp.length;i++) {
			for(int j=1;j<=n;j++) {
				dp[i][j]=dp[i-1][dp[i-1][j]];
			}
		}
	}
	static int lca(int u, int v) {
		if(level[u]>level[v]) {
			int temp = u;
			u=v;
			v=temp;
		}
		int diff = level[v]-level[u];
		while(diff>0) {
			int log = log(diff);
			v=  dp[log][v];
			diff -=(1<<log);
		}
		while(u!=v) {
			int i=log(level[u]);
			for(;i>0&&dp[i][v]==dp[i][u];) {
				i--;
			}
//			System.out.println(i);
			u=dp[i][u];
			v=dp[i][v];
		}
		return u;
	}
	static int dist(int u,int v) {
		return level[u]+level[v]-2*(level[lca(u,v)]);
	}
	
	
	/*						Templates						*/
	static class Pair<S extends Comparable<S>,T extends Comparable<T>> implements Comparable<Pair<S,T>>{
		S first;
		T second;
		public Pair() {
			this.first=null;
			this.second =null;
		}
		public Pair(S first) {
			this.first = first;
			this.second =null;
		}
		public Pair(S first, T second) {
			this.first = first;
			this.second = second;
		}
		public int compareTo(Pair<S,T> o) {
			if(this.first.compareTo(o.first)==0) {
				return this.second.compareTo(o.second);
			}
			return this.first.compareTo(o.first);
		}
		public String toString() {
			return "{"+this.first.toString()+","+this.second.toString()+"}";
		}
	}
	static int log(int N) {
		// TODO Auto-generated method stub
		return 31- Integer.numberOfLeadingZeros(N);
	}
	static int lowerBound(int[] a, int x,int lf,int rg) {
		int l = lf-1, r = rg+1;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				//if (a[c] > x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
	static int upperBound(int[] a, int x,int lf,int rg) {
		int l = lf-1, r = rg+1;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int lowerBound(long[] a, long x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int upperBound(long[] a, long x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int lowerBound(double[] a, double x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] < x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static int upperBound(double[] a, double x) {
		int l = -1, r = a.length;
		while (r - l > 1) {
			int c = (l + r) / 2;
			if (a[c] <= x) {
				l = c;
			} else {
				r = c;
			}
		}
		return r;
	}
 
	static <T> int lowerBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) >= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) >= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) >= 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey Maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int upperBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) > 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) > 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) > 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey Maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int rupperBound(List<T> ls, T x) throws RuntimeException {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) < 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) < 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) < 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
 
	static <T> int rlowerBound(List<T> ls, T x) {
		if (ls.size() == 0)
			return -1;
		if (ls.get(0) instanceof Integer) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Integer) t1).compareTo((Integer) t2) <= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Long) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Long) t1).compareTo((Long) t2) <= 0 ? 1 : -1);
		} else if (ls.get(0) instanceof Double) {
			return ~Collections.binarySearch(ls, x, (t1, t2) -> ((Double) t1).compareTo((Double) t2) <= 0 ? 1 : -1);
		} else {
			System.err.println(
					String.format("%s:Arey maa chudi padi hai", Thread.currentThread().getStackTrace()[1].getMethodName()));
			throw new RuntimeException();
		}
	}
	public static int[] merge(int[] one,int[] two){
		int[] res = new int[one.length+two.length];
		int i = 0;
		int j = 0;
		int k = 0;
		
		while(i<one.length&&j<two.length){
			if(one[i]<two[j]){
				res[k] = one[i];
				i++;
				k++;
			}
			else{
				res[k] = two[j];
				j++;
				k++;
			}
		}
		
		if(i==one.length){
			while(j<two.length){
				res[k] = two[j];
				j++;
				k++;
			}
		}
		else{
			while(i<one.length){
				res[k] = one[i];
				k++;
				i++;
			}
		}
		return res;
	}
	public static int[] mergesort(int[] arr, int l, int r){
		if(l==r){
			int[] br = new int[1];
			br[0] = arr[l];
			return br;
		}
		int mid = (l+r)/2;
		int[] fh = mergesort(arr,l,mid);
		int[] sh = mergesort(arr,mid+1,r);
		
		return merge(fh,sh);
	}
	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; 
        } 
    }

}
