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.*;
import java.io.*;

/*
15 0
3 11
3 1
3 7
3 4
1 2
11 15
11 13
11 6
15 14
6 9
7 12
7 8
12 10
8 5
 */

public class XeniaAndTree
{
	
	static ArrayList<Integer>[] tree;
	static int[] size;
	static int[] parent;
	static int[] ans;
	static boolean[] v;

	static int n, d, depth[], lift[][];
	
	public static void main(String[] args)
	{
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt();
		int m = scan.nextInt();
		tree = new ArrayList[n];
		for(int i = 0; i < n; i++) tree[i] = new ArrayList<Integer>();
		for(int i = 0; i < n-1; i++) {
			int u = scan.nextInt()-1;
			int v = scan.nextInt()-1;
			tree[u].add(v);
			tree[v].add(u);
		}
		depth = new int[n];
		d = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 2;
		lift = new int[d][n];
		for(int i = 0 ; i < d ; i++) Arrays.fill(lift[i], -1);
		
		Deque<Integer> q = new ArrayDeque<>();
		q.add(0);
		while(!q.isEmpty()) {
			int u = q.pop();
			for(int v : tree[u]) {
				if(lift[0][u] != v) {
					lift[0][v] = u;
					depth[v] = depth[u] + 1;
					q.add(v);
				}
			}
		}
		for(int k = 0 ; k < d - 1 ; k++)
			for(int i = 0 ; i < n ; i++)
				if(lift[k][i] != -1)
					lift[k + 1][i] = lift[k][lift[k][i]];
		
		
		size = new int[n];
		parent = new int[n];
		v = new boolean[n];
		decomp(0, -1);
		ans = new int[n];
		Arrays.fill(ans, 123456789);
		
		int curr = 0;
		while(curr != -1) {
			ans[curr] = dist(curr, 0);
			curr = parent[curr];
		}
//		System.out.println(Arrays.toString(parent));
		for(int i = 0; i < m; i++) {
			int type = scan.nextInt();
			int u = scan.nextInt()-1;
			if(type == 1) {
				curr = u;
				while(curr != -1) {
					ans[curr] = Math.min(ans[curr], dist(u, curr));
					curr = parent[curr];
				}
			}
			else {
				curr = u;
				int res = 123456789;
				while(curr != -1) {
					res = Math.min(res, dist(u, curr)+ans[curr]);
					curr = parent[curr];
				}
				out.println(res);
			}
		}
		out.flush();
	}
	
	static int lca(int u, int v) {
		if(depth[v] > depth[u]) return lca(v, u);
		u = walk(u, depth[u] - depth[v]);
		if(u == v) return u;
		for(int k = d - 1 ; k >= 0 ; k--) {
			if(lift[k][u] != lift[k][v]) {
				u = lift[k][u];
				v = lift[k][v];
			}
		}
		return lift[0][u];
	}
	
	static int walk(int u, int k) {
		for(int i = 0 ; i < d && u != -1 ; i++) if((k & (1 << i)) > 0) u = lift[i][u];
		return u;
	}
	
	static int dist(int u, int v) { return depth[u] + depth[v] - (2 * depth[lca(u, v)]); }
	
	static int findCentroid(int cur, int prev, int n) {
		for(int to : tree[cur]) 
			if(!v[to] && to != prev && size[to] > n/2) 
				return findCentroid(to, cur, n);
		return cur;
	}
	
	static int decomp(int curr, int prev) {
		int n = getSizes(curr, prev);
		int centroid = findCentroid(curr, prev, n);
		v[centroid] = true;
		parent[centroid] = prev;
		for(int i = 0; i < tree[centroid].size(); i++) {
			int to = tree[centroid].get(i);
			if(!v[to]) decomp(to, centroid);
		}
		return centroid;
	}
	
	static int getSizes(int c, int p) {
		size[c] = 1;
		for(int i = 0; i < tree[c].size(); i++) {
			int to = tree[c].get(i);
			if(to != p && !v[c])
				size[c] += getSizes(to, c);
		}
		return size[c];
	}

	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}
