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

public class XeniaAndTree {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int MAX = 20;
	static int[][] P;
	static int[] level, r, cent, aux;
	static HashSet<Integer>[] g;
	static int N, M, t;
	static int inf = 999999999;
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		g = new HashSet[N];
		level = new int[N];
		r = new int[N];
		cent = new int[N];
		aux = new int[N];
		P = new int[N][MAX];
		level[0] = 0;
		P[0][0] = 0;
		t = 0;
		for(int i=0;i<N;i++){
			g[i]=new HashSet<Integer>();
			r[i] = inf;
		}
		for(int i=0;i<N-1;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			g[a].add(b);
			g[b].add(a);
		}
		calc(0);
		init_lca();
		centDecomp(0, -1);
		paint(0);
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken())-1;
			if(a == 1){
				paint(b);
			}
			else{
				int resp = query(b);
				sb.append(resp);
				sb.append("\n");
			}
		}
		System.out.println(sb.toString());

	}
	public static int query(int u){
		int x = u;
		int out = inf;
		while(true){
			int d = dist(x,u) + r[x];
			if(d < out){
				out = d;
			}
			if(x == cent[x]) break;
			x = cent[x];
		}
		return out;
	}

	public static void paint(int u){
		int x = u;
		while(true){
			int d = dist(x,u);
			if(d < r[x]){
				r[x] = d;
			}
			if(x == cent[x]) break;
			x = cent[x];
		}
	}

	public static void centDecomp(int s,int p){
		t = 0;
		dfsA(s,s);
		int c = dfsB(s, p);
		if (p == -1) p = c;
		cent[c] = p;
		for(int v : g[c]){
			g[v].remove(c);
			centDecomp(v, c);
		}
		g[c].clear();
	}

	public static void dfsA(int s, int p){
		t++;
		aux[s] = 1;
		for( int v : g[s]){
			if(v != p){
				dfsA(v, s);
				aux[s] += aux[v];
			}
		}
	}

	public static int dfsB(int s, int p){
		for(int v:g[s]){
			if(v != p && aux[v] > t/2){
				return dfsB(v,s);
			}
		}
		return s;
	}


	public static void calc(int u){
		for(int v : g[u]){
			if(v != P[u][0]){
				P[v][0] = u;
				level[v] = level[u] + 1;
				calc(v);
			}
		}
	}

	public static int dist(int A, int B){
		int C = lca(A,B);
		//System.out.println(C);
		return level[A] + level[B] - 2*level[C];
	}

	public static int anc_dist(int A, int dist) {
		for (int i = 0; i < MAX; i++) {
			if (((1 << i) & dist) != 0) {
				A = P[A][i];
			}
		}
		return A;
	}

	public static int lca(int A, int B) {

		if (level[A] < level[B]){
			int aux = A;
			A = B;
			B = aux;
		}
		int dif = level[A] - level[B];
		A = anc_dist(A, dif);
		if (A == B){
			return A;
		}

		for (int k = MAX-1; k >= 0; --k) {
			if (P[A][k] != P[B][k]) {
				A = P[A][k];
				B = P[B][k];
			}
		}

		return P[A][0];
	}

	public static void init_lca() {
		for (int k = 1; k < MAX; ++k)
			for (int i = 0; i < N; ++i)
				P[i][k] = P[P[i][k-1]][k-1];
	}

	public static int anc_level(int A, int l) {
		for (int k = MAX-1; k >= 0; --k) {
			if (level[P[A][k]] >= l)
				A = P[A][k];
		}
		return A;
	}
}
