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
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF342E extends PrintWriter {
	CF342E() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF342E o = new CF342E(); o.main(); o.flush();
	}

	int[] oo, oj; int __ = 1;
	int link(int o, int j) {
		oo[__] = o; oj[__] = j;
		return __++;
	}
	int[] ae, sz, dd_; int[][] cc, dd; int[] kk;
	boolean[] used;
	void init(int n) {
		int m = n - 1;
		oo = new int[1 + m * 2]; oj = new int[1 + m * 2];
		ae = new int[n]; sz = new int[n];
		dd_ = new int[n]; Arrays.fill(dd_, n);
		int ln = 0;
		while (1 << ln + 1 <= n)
			ln++;
		kk = new int[n]; cc = new int[n][ln]; dd = new int[n][ln];
		used = new boolean[n];
	}
	int c_;
	void dfs(int p, int i, int n, int k, int c, int d) {
		if (k > 0) {
			kk[i] = k; cc[i][k - 1] = c; dd[i][k - 1] = d;
		}
		boolean centroid = true;
		sz[i] = 1;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p && !used[j]) {
				dfs(i, j, n, k, c, d + 1);
				if (sz[j] * 2 > n)
					centroid = false;
				sz[i] += sz[j];
			}
		}
		if ((n - sz[i]) * 2 > n)
			centroid = false;
		if (centroid)
			c_ = i;
	}
	void cd(int i, int n, int k, int c) {
		dfs(-1, i, n, k, c, 1);
		used[c = c_] = true;
		for (int o = ae[c]; o != 0; o = oo[o]) {
			i = oj[o];
			if (!used[i])
				cd(i, sz[i] < sz[c] ? sz[i] : n - sz[c], k + 1, c);
		}
	}
	void update(int i) {
		dd_[i] = 0;
		for (int h = 0; h < kk[i]; h++) {
			int j = cc[i][h];
			dd_[j] = Math.min(dd_[j], dd[i][h]);
		}
	}
	int query(int i) {
		int ans = dd_[i];
		for (int h = 0; h < kk[i]; h++) {
			int j = cc[i][h];
			ans = Math.min(ans, dd[i][h] + dd_[j]);
		}
		return ans;
	}
	void main() {
		int n = sc.nextInt();
		int q = sc.nextInt();
		init(n);
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ae[i] = link(ae[i], j);
			ae[j] = link(ae[j], i);
		}
		cd(0, n, 0, -1);
		update(0);
		while (q-- > 0) {
			int t = sc.nextInt();
			int i = sc.nextInt() - 1;
			if (t == 1)
				update(i);
			else
				println(query(i));
		}
	}
}
