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.math.*;
import java.security.KeyStore.Entry;
import java.util.*;

public class CODEFORCES {
	private InputStream is;
	private PrintWriter out;

	int p[][], parent[], n, k, depth[], pa[], sub[], count = 0;
	ArrayList<Integer> a[];
	boolean cm[];

	void pre() {
		for (int i = 0; i < n; i++)
			p[i][0] = parent[i];
		for (int i = 1; i < k; i++) {
			for (int j = 0; j < n; j++)
				p[j][i] = p[p[j][i - 1]][i - 1];
		}
	}

	int lca(int u, int v) {
		if (depth[u] < depth[v]) {
			int t = u;
			u = v;
			v = t;
		}
		int l = 1, d = 0;
		while ((1 << l) <= depth[u])
			l++;
		l--;
		for (int i = l; i >= 0; i--) {
			if (depth[u] - depth[v] >= 1 << i) {
				u = p[u][i];
				d += 1 << i;
			}
		}
		if (u == v)
			return d;
		for (int i = l; i >= 0; i--) {
			if (p[u][i] != p[v][i]) {
				u = p[u][i];
				v = p[v][i];
				d += (1 << (i + 1));
			}
		}
		return d+2;
	}

	void dfs(int p, int x) {
		for (int i : a[p]) {
			if (i == x)
				continue;
			depth[i] = depth[p] + 1;
			parent[i] = p;
			dfs(i, p);
		}
	}

	void dfs2(int p, int x) {
		sub[p] = 0;
		sub[p]++;
		count++;
		for (int i : a[p]) {
			if (i != x && !cm[i]) {
				dfs2(i, p);
				sub[p] += sub[i];
			}
		}
	}

	int get(int r, int x) {
		boolean v = false;
		int hv = -1;
		for (int i : a[r]) {
			if (i != x && !cm[i]) {
				if (sub[i] > (count >> 1))
					v = true;
				if (hv == -1 || sub[i] > sub[hv])
					hv = i;
			}
		}
		if (!v && sub[r] >= (count >> 1))
			return r;
		return get(hv, r);
	}

	int getC(int r) {
		count = 0;
		dfs2(r, r);
		int c = get(r, r);
		cm[c] = true;
		return c;
	}

	int decompose(int r) {
		int cen = getC(r);
		for (int i : a[cen]) {
			if (cm[i])
				continue;
			int c = decompose(i);
			pa[c] = cen;
		}
		return cen;
	}

	@SuppressWarnings("unchecked")
	void ini() {
		a = new ArrayList[n];
		for (int i = 0; i < n; i++)
			a[i] = new ArrayList<Integer>();
		parent = new int[n];
		depth = new int[n];
		k = (int) (Math.log(n) / Math.log(2)) + 3;
		p = new int[n][k];
		cm = new boolean[n];
		pa = new int[n];
		sub = new int[n];
		for (int i = 0; i < n; i++)
			pa[i] = i;
	}

	void solve() {
		n = ni();
		int m = ni();
		ini();
		for (int i = 1; i < n; i++) {
			int x = ni() - 1, y = ni() - 1;
			a[x].add(y);
			a[y].add(x);
		}
		dfs(0, 0);
		pre();
		decompose(0);
		int ans[] = new int[n];
		Arrays.fill(ans, (int) 1e6);
		int x = 0, u = 0;
		while (x != pa[x]) {
			ans[x] = Math.min(ans[x], lca(x, u));
			x = pa[x];
		}
		ans[x] = Math.min(ans[x], lca(x, u));
		while (m-- > 0) {
			int t = ni();
			x = ni() - 1;
			if (t == 1) {
				u = x;
				while (x != pa[x]) {
					ans[x] = Math.min(ans[x], lca(x, u));
					x = pa[x];
				}
				ans[x] = Math.min(ans[x], lca(x, u));
			} else {
				int mn = (int) 1e6;
				u = x;
				while (x != pa[x]) {
					mn = Math.min(mn, lca(x, u) + ans[x]);
					x = pa[x];
				}
				mn = Math.min(mn, lca(x, u) + ans[x]);
				out.println(mn);
			}
		}
	}

	void soln() {
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new CODEFORCES().soln();
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}