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.util.*;

public class E {
	static final int LOG = 18;
	static List<List<Integer>> tree;
	static int [] tin;
	static int [] tout;
	static int [] dist;
	static int [] reddist;
	static boolean [] red;
	static int [][] up;
	static int timer;
	static void dfs(int v, int p){
		tin[v] = ++timer;
		if (p != -1){
			up[v][0] = p;
			dist[v] = dist[p] + 1;
			for (int i = 1; i < LOG; ++i){
				up[v][i] = up[up[v][i - 1]][i - 1];
			}
		}
		for (int adj : tree.get(v)){
			if (adj != p){
				dfs(adj, v);
			}
		}
		tout[v] = ++timer;
	}
	static void bfs(Queue<Integer> queue){
		while (!queue.isEmpty()){
			final int v = queue.poll();
			for (int a : tree.get(v)){
				if (reddist[a] > reddist[v] + 1){
					reddist[a] = reddist[v] + 1;
					queue.offer(a);
				}
			}
		}
	}
	static boolean isParent(int a, int b){
		return tin[a] <= tin[b] && tout[a] >= tout[b];
	}
	static int lca(int a, int b){
		if (isParent(a, b)){
			return a;
		}
		if (isParent(b, a)){
			return b;
		}
		int res = a;
		for (int i = LOG - 1; i >= 0; --i){
			if (!isParent(up[res][i], b)){
				res = up[res][i];
			}
		}
		return up[res][0];
	}
	static int dist(int a, int b){
		final int lca = lca(a, b);
		return dist[a] + dist[b] - 2*dist[lca];
	}
	public static void main(String [] args){
		final Scanner s = new Scanner(System.in);
		final int n = s.nextInt();
		final int m = s.nextInt();
		tree = new ArrayList<List<Integer>>(n);
		for (int i = 0; i < n; ++i){
			tree.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < n - 1; ++i){
			final int a = s.nextInt() - 1;
			final int b = s.nextInt() - 1;
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		tin = new int[n];
		tout = new int[n];
		dist = new int[n];
		up = new int[n][LOG];
		dfs(0, -1);
		reddist = dist.clone();
		red = new boolean[n];
		red[0] = true;
		final int sqrt = (int)Math.sqrt(m) + 1;
		final Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 0, sqrtbatch = 0; i < m; ++i, ++sqrtbatch){
			if (sqrtbatch >= sqrt){
				bfs(queue);
				sqrtbatch = 0;
			}
			final int t = s.nextInt();
			final int v = s.nextInt() - 1;
			if (t == 1){
				red[v] = true;
				reddist[v] = 0;
				queue.add(v);
			}else{
				int min = reddist[v];
				for (int j : queue){
					min = Math.min(min, dist(j, v));
				}
				System.out.println(min);
			}
		}
		s.close();
	}
}
