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 XeniaAndTree {
	
	static int[] depth;
	static int n,maxJ;
	static ArrayList<Integer>[] a;
	static int[][] jump;
	static final long oo=Long.MAX_VALUE/2-5;
	
	public static void main(String[] args) {
		FastScanner scan=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		
		n=scan.nextInt();
		int q=scan.nextInt();
		a=new ArrayList[n];
		for(int i=0;i<n;i++) a[i]=new ArrayList<>();
		for(int i=0;i<n-1;i++) {
			int u=scan.nextInt()-1, v=scan.nextInt()-1;
			a[u].add(v);
			a[v].add(u);
		}
		maxJ=Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
		jump=new int[n][maxJ+1];
		for(int[] j:jump) Arrays.fill(j,-1);

		depth=new int[n];
		bfs();
		
		for(int j=1;j<=maxJ;j++) {
			for(int i=0;i<n;i++) {
				int mid=jump[i][j-1];
				if(mid!=-1) jump[i][j]=jump[mid][j-1];
			}
		}
		size=new int[n];
		dead=new boolean[n];
		par=new int[n];
		Arrays.fill(par,-1);
		
		res=new long[n];
		Arrays.fill(res,oo);
		
		centroid=go(0);
		//System.out.println(Arrays.toString(par));
		
		paint(0);
		
		for(int i=0;i<q;i++) {//ohmigod im bad
			int x=scan.nextInt(), y=scan.nextInt()-1;
			if(x==1) paint(y);
			else query(y,out);
		}
		out.close();
	}
	static int centroid;
	static long[] res;
	public static void query(int i, PrintWriter out) {
		long ans=oo;
		int up=i;
		while(true) {
			//System.out.println("QUERY UP "+up);
			ans=Math.min(ans,dist(up,i)+res[up]);
			if(up==centroid) break;
			up=par[up];
		}
		out.println(ans);
	}
	public static void paint(int i) {
		int up=i;
		while(true) {
			//System.out.println("PAINTING UP "+up);
			res[up]=Math.min(res[up],dist(up,i));
			if(up==centroid) break;
			up=par[up];
		}
	}
	static boolean[] dead;
	static int[] size;
	
	public static int cent(int i, int prev, int totalSize) {
		for(int nxt:a[i]) {
			if(!dead[nxt]&&size[nxt]>totalSize/2&&nxt!=prev) return cent(nxt,i,totalSize);
		}
		return i;
	}
	public static int updSize(int i, int prev) {
		size[i]=1;
		for(int nxt:a[i]) {
			if(!dead[nxt]&&nxt!=prev) size[i]+=updSize(nxt,i);
		}
		return size[i];
	}
	
	static int[] par;
	public static int go(int at) {
		int curSize=updSize(at,-1);
		int cent=cent(at,-1,curSize);
		dead[cent]=true;
		
		for(int nxt:a[cent]) {
			if(!dead[nxt]) {
				par[go(nxt)]=cent;
			}
		}
		return cent;
	}
	public static long dist(int i, int j) {
		return depth[i]+depth[j]-2*depth[lca(i,j)];
	}
	public static int lca(int i, int j) {
//		System.out.println("ahahhaha");
		if(depth[i]>depth[j]) i=walk(i,depth[i]-depth[j]);
		if(depth[j]>depth[i]) j=walk(j,depth[j]-depth[i]);
//		System.out.println(i+" "+j);
		if(i==j) return i;

		for(int k=maxJ;k>=0;k--) {
			if(jump[i][k]!=jump[j][k]) {
				i=jump[i][k];
				j=jump[j][k];
			}
		}
		return jump[i][0];
	}
	public static int walk(int n, int dist) {
		for(int i=0;i<=maxJ;i++) {
			if((dist&1<<i)>0&&jump[n][i]!=-1) {
				n=jump[n][i];
			}
		}
		return n;
	}
	public static void bfs() {
		ArrayDeque<Integer> q=new ArrayDeque<>();
		boolean[] v=new boolean[n];
		v[0]=true;
		q.offer(0);

		while(!q.isEmpty()) {
			int u=q.poll();
			for(int nxt:a[u]) {
				if(v[nxt]) continue;
				depth[nxt]=depth[u]+1;
				jump[nxt][0]=u;
				v[nxt]=true;
				q.offer(nxt);
			}
		}
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}

		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}

		public int nextInt() {return Integer.parseInt(next());}

		public long nextLong() {return Long.parseLong(next());}

		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
}