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 XeniaTree {
	public static int next(StringTokenizer st) {
		return Integer.parseInt(st.nextToken());
	}

	static int N, M;
	static ArrayList<Integer>[] adjlist;
	static boolean[] visited;
	static int[] size;
	static ArrayList<Integer>[] centAdjlist;
	static int[][] dist;
	static int[] centParent;
	static long[] ans;
	static int[] lvl;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		// input file name goes above

		StringTokenizer st = new StringTokenizer(sc.readLine());
		N = next(st);
		M = next(st);
		visited = new boolean[N];
		ans = new long[N];
		lvl = new int[N];
		centParent = new int[N];
		dist = new int[N][32];
		size = new int[N];
		centAdjlist = new ArrayList[N];
		adjlist = new ArrayList[N];
		for(int i = 0; i < N; i++) {
			centAdjlist[i] = new ArrayList<>();
			adjlist[i] = new ArrayList<>();
			ans[i] = Integer.MAX_VALUE;
		}
		for(int i = 1; i < N; i++) {
			st = new StringTokenizer(sc.readLine());
			int x = next(st);
			int y = next(st);
			x--; y--;
			adjlist[y].add(x);
			adjlist[x].add(y);
		}
		decompose(0);
		
		activate(0);
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(sc.readLine());
			int q = next(st);
			int x = next(st);
			x--;
			if(q == 1) {
				activate(x);
			}
			else {
				System.out.println(findMin(x));
			}
		}
		
		sc.close();
	}
	
	public static void activate(int v) {
		ans[v] = 0;
		int curr = v;
		while(centParent[curr] != -1) {
			//System.out.println(v + " " + curr + " " + centParent[curr] + " " + ans[centParent[curr]]);
			ans[centParent[curr]] = Math.min(ans[centParent[curr]], dist[v][lvl[curr]-1]);
			curr = centParent[curr];
		}
	}
	
	public static long findMin(int v) {
		long res = ans[v];
		int curr = centParent[v];
		while(curr != -1) {
			//System.out.println(curr + " " + centParent[curr]);
			res = Math.min(res, dist[v][lvl[curr]] + ans[curr]);
			curr = centParent[curr];
		}
		return res;
	}
	
	public static void decompose(int entry) {
		decompose(entry, -1);
	}
	
	public static void decompose(int entryPoint, int p) {
		findSize(entryPoint, p);
		int cent = findCentroid(entryPoint, -1, size[entryPoint]);
		visited[cent] = true;
		if(p != -1) {
			centParent[cent] = p;
			centAdjlist[cent].add(p);
			centAdjlist[p].add(cent);
			lvl[cent] = lvl[p] + 1;
		}
		else {
			centParent[cent] = -1;
			lvl[cent] = 0;
		}
		//bfs
		bfs(cent);
		
		for(int c : adjlist[cent]) {
			if(visited[c]) continue;
			decompose(c, cent);
		}
	}
	
	public static void bfs(int centroid) {
		Queue<Integer> q = new LinkedList<Integer>();
		dist[centroid][lvl[centroid]] = 0;
		q.add(centroid);
		while(!q.isEmpty()) {
			int v = q.poll();
			for(int c : adjlist[v]) {
				if(visited[c] || dist[c][lvl[centroid]] != 0) {
					continue;
				}
				dist[c][lvl[centroid]] = dist[v][lvl[centroid]] + 1;
				q.add(c);
			}
		}
	}
	
	public static int findSize(int v, int p) {
		size[v] = 1;
		for(int c : adjlist[v]) {
			if(c == p || visited[c]) continue;
			size[v] += findSize(c, v);
		}
		return size[v];
	}
	
	public static int findCentroid(int v, int p, int n) {
		for(int c : adjlist[v]) {
			if(c == p || visited[c]) {
				continue;
			}
			if(size[c] > n/2) {
				return findCentroid(c, v, n);
			}
		}
		return v;
	}
}


