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
/*
javac E542.java && java E542
*/

import java.io.*;
import java.util.*;

public class E542 {
	public static void main(String[] args) { new E542(); }
	FS in = new FS();
	PrintWriter out = new PrintWriter(System.out);

	int n, m, oo = 1 << 20;
	int[] dp;
	int l, r, z, mx, lg;
	int[] p, cp, q, off, sz;
	int[] depth;
	int[][] lift;
	boolean[] done;
	ArrayList<Integer>[] adj;

	E542() {
		n = in.nextInt();
		m = in.nextInt();

		adj = new ArrayList[n];
		for (int i = 0; i < n; i++)
			adj[i] = new ArrayList<>();
		for (int i = 0; i < n - 1; i++) {
			int u = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			adj[u].add(v);
			adj[v].add(u);
		}

		p = new int[n];
		cp = new int[n];
		q = new int[n << 1];
		off = new int[n];
		done = new boolean[n];
		decomp();

		depth = new int[n];
		lg = 0; while (n >= (1 << lg++));
		lift = new int[lg][n];
		l = 0; r = 0;
		q[r++] = 0;
		q[r++] = 0;
		int node, par;
		while (l != r) {
			node = q[l++];
			par = q[l++];
			for (int i : adj[node])
				if (i != par) {
					depth[i] = 1 + depth[node];
					lift[0][i] = node;
					for (int j = 1; j < lg; j++)
						if (depth[i] >= (1 << j))
							lift[j][i] = lift[j - 1][lift[j - 1][i]];
					q[r++] = i;
					q[r++] = node;
				}
		}

		int t, x, mn;
		dp = new int[n];
		Arrays.fill(dp, oo);
		z = 0;
		while (z != -1) {
			dp[z] = min(dp[z], dist(z, 0));
			z = cp[z];
		}
		while (m-- > 0) {
			t = in.nextInt();
			x = in.nextInt() - 1;
			if (t == 1) {
			 	z = x;
				while (z != -1) {
					dp[z] = min(dp[z], dist(z, x));
					z = cp[z];
				}
			}
			if (t == 2) {
				mn = oo; z = x;
				while (z != -1) {
					mn = min(mn, dp[z] + dist(z, x));
					z = cp[z];
				}
				out.println(mn);
			}
		}
		out.close();
	}
	
	int dist(int x, int y) {
		return depth[x] + depth[y] - 2 * depth[lca(x, y)];
	}
	int lca(int x, int y) {
		if (x == y) return x;
		if (depth[x] < depth[y])
			x = y^(x^(y = x));
		int up = depth[x] - depth[y];
		for (int i = lg - 1; i >= 0; i--)
			if ((up | (1 << i)) == up)
				x = lift[i][x];
		if (x == y) return x;
		for (int i = lg - 1; i >= 0; i--)
			if (lift[i][x] != lift[i][y]) {
				x = lift[i][x];
				y = lift[i][y];
			}
		return lift[0][x];
	}
	
	void decomp() {
		sz = new int[n];

		int x, y, z;
		int lb = 0, rb = 0;
		int[] build = new int[n << 1];
		build[rb++] = 0; 
		build[rb++] = 0;
		while (lb != rb) {
			x = build[lb++];
			y = build[lb++];
			z = centroid(x);
			if (x != y) cp[z] = y;
			else cp[z] = -1;
			done[z] = true;
			for (int w : adj[z])
				if (!done[w]) {
					build[rb++] = w;
					build[rb++] = z;
				}
		}
	}
	int centroid(int x) {
		dfs(x, x);
		l = 0; r = 0;
		q[r++] = x;
		while (l != r) {
			z = q[l++];
			mx = sz[x] - sz[z];
			for (int w : adj[z])
				if (w != p[z] && !done[w]) {
					mx = max(mx, sz[w]);
					q[r++] = w;
				}
			if ((mx << 1) <= sz[x])
				return z;
		}
		return -1;
	}
	void dfs(int x, int y) {
		l = 0; r = 0;
		q[r++] = x;
		p[x] = y;
		while (r != 0) {
			x = q[--r];
			sz[x] = 1; y = p[x];
			for (int i : adj[x])
				if (i != y && !done[i]) {
					q[r++] = i;
					p[i] = x;
				}
			if (x != y)
				off[l++] = x;
		}
		while (l != 0) {
			z = off[--l];
			sz[p[z]] += sz[z];
		}
	}
	
	int abs(int x) { return x < 0 ? -x : x; }
	long abs(long x) { return x < 0 ? -x : x; }
	double abs(double x) { return x < 0 ? -x : x; }
	int min(int x, int y) { return x < y ? x : y; }	
	int max(int x, int y) { return x > y ? x : y; }
	long min(long x, long y) { return x < y ? x : y; }	
	long max(long x, long y) { return x > y ? x : y; }
	double min(double x, double y) { return x < y ? x : y; }
	double max(double x, double y) { return x > y ? x : y; }
	int gcd(int x, int y) { while (y > 0) { x = y^(x^(y = x)); y %= x; } return x; }
	long gcd(long x, long y) { while (y > 0) { x = y^(x^(y = x)); y %= x; } return x; }
	long lcm(int x, int y) { return ((long) x / gcd(x, y)) * y; }
	long lcm(long x, long y) { return (x / gcd(x, y)) * y; }

	void sort(int[] arr) {
		int sz = arr.length, j;
		Random r = new Random();
		for (int i = 0; i < sz; i++) {
			j = r.nextInt(i + 1);
			arr[i] = arr[j]^(arr[i]^(arr[j] = arr[i]));
		} Arrays.sort(arr);
	}

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