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 N, D, M;
	static ArrayList<Integer>[] adj;
	static TreeSet<Integer>[] adj2;
	static int[][] par;
	static int[] depth;
	static int[] centroidParent;
	static int[] sub;
	static int NN;
	static int[] ans;
	public static void main(String[] args) throws Exception{
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(f.readLine());
		N = Integer.parseInt(st.nextToken());
		D = Integer.numberOfTrailingZeros(Integer.highestOneBit(N));
		M = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[N];
		adj2 = new TreeSet[N];
		sub = new int[N];
		centroidParent = new int[N];
		ans = new int[N];
		
		Arrays.fill(ans, (int)(1e5 + 5));
		
		for(int i = 0; i < N; i++) {
			adj[i] = new ArrayList<Integer>();
			adj2[i] = new TreeSet<Integer>();
		}
		
		for(int i = 0; i < N - 1; i ++) {
			st = new StringTokenizer(f.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			adj[x].add(y);
			adj[y].add(x);
			adj2[x].add(y);
			adj2[y].add(x);
		}
		
		createParentArray();
		
		constructCentroidTree(0, -1);
		
		update(0);
		
		for(int i = 0; i < M; i ++) {
			st = new StringTokenizer(f.readLine());
			int type = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken()) - 1;
			
			if(type == 1) {
				update(u);
			}
			else {
				System.out.println(query(u));
			}
		}
	}
	
	static void update(int u) {
		int x = u;
		while(x != -1) {
			ans[x] = Math.min(ans[x], dist(u,x));
			x = centroidParent[x];
		}
	}
	
	static int query(int u) {
		int ret = (int)(1e5 + 5);
		int x = u;
		while(x != -1) {
			ret = Math.min(ret, dist(u,x) + ans[x]);
			x = centroidParent[x];
		}
		return ret;
	}
	
	static void dfs1(int i, int p) {
		sub[i] = 1;
		NN ++;
		Iterator<Integer> it = adj2[i].iterator();
		while(it.hasNext()) {
			int k = it.next();
			if(k != p) {
				dfs1(k,i);
				sub[i] += sub[k];
			}
		}
	}
	
	static int dfs2(int i, int p) {
		Iterator<Integer> it = adj2[i].iterator();
		while(it.hasNext()) {
			int k = it.next();
			if(k != p && sub[k] > NN/2) {
				return dfs2(k, i);
			}
		}
		return i;
	}
	
	static void constructCentroidTree(int root, int p) {
		NN = 0;
		dfs1(root, root);
		int centroid = dfs2(root, root);
		centroidParent[centroid] = p;
		Iterator<Integer> it = adj2[centroid].iterator();
		while(it.hasNext()) {
			int k = it.next();
			adj2[k].remove(centroid);
			constructCentroidTree(k, centroid);
		}
		adj2[centroid].clear();
	}
	
	static void createParentArray() {
		par = new int[D+1][N];
		depth = new int[N];
		for(int[] dd:par) {
			Arrays.fill(dd, -1);
		}
		
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] vis = new boolean[N];
		q.add(0);
		vis[0] = true;
		while(!q.isEmpty()) {
			int i = q.remove();
			for(int j: adj[i]) {
				if(!vis[j]) {
					q.add(j);
					vis[j] = true;
					depth[j] = depth[i] + 1;
					par[0][j] = i;
				}
			}
		}
		
		for(int k=1;k<=D;k++) {
			for(int i = 0;i<N;i++) {
				int mid = par[k-1][i];
				if(mid != -1) {
					par[k][i] = par[k-1][mid];
				}
			}
		}
	}
	
	static int walk(int i, int k) {
		for(int d = 0; d<=D && i != -1; d++) {
			if(((1 << d) & k) > 0) {
				i = par[d][i];
			}
		}
		return i;
	}
	
	static int lca(int i, int j) {
		if(depth[i] > depth[j]) {
			i = walk(i,depth[i] - depth[j]);
		}
		if(depth[j] > depth[i]) {
			j = walk(j,depth[j] - depth[i]);
		}	
		if(i == j) {
			return i;
		}
		
		for(int d=D;d >=0;d--) {
			if(par[d][i] != par[d][j]) {
				i = par[d][i];
				j = par[d][j];
			}
		}
		
		return par[0][i];
	}
	
	static int dist(int u, int v) {
		return depth[u] + depth[v] - 2*depth[lca(u,v)];
	}
	

}
