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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.BufferedInputStream;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		BufferedInputStream in = new BufferedInputStream(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskE {
		int[][] g;
		int[] h;
		LCA2 lca = null;
		int n;
		int[] pc;
		int[] min;
		public static int INF = (int) 1e9;

		int dist(int u, int v) {
			int p = lca.getLCA(u, v);
			return h[u] + h[v] - 2 * h[p];
		}

		void paintRed(int u) {
			min[u] = 0;

			int p = pc[u], d;
			while (p != -1) {

				d = dist(p, u);
				min[p] = Math.min(min[p], d);
				p = pc[p];
			}
		}

		int query(int u) {
			int re = min[u];
			int u0 = u;
			while (pc[u] != -1) {
				u = pc[u];
				re = Math.min(re, min[u] + dist(u0, u));
			}
			return re;
		}

		public void solve(int testNumber, BufferedInputStream _in, PrintWriter out) {

			InputReader in = new InputReader(_in);
			long startTime = System.currentTimeMillis();
			n = in.nextInt();
			int q = in.nextInt();
			int[] from = new int[n - 1];
			int[] to = new int[n - 1];

			for (int i = 0; i < n - 1; ++i) {
				from[i] = in.nextInt() - 1;
				to[i] = in.nextInt() - 1;
			}
			g = Graphs.packU(n, from, to);
			lca = new LCA2(n, 0, g);
			h = lca.dep;

			pc = Graphs.buildCentroidTree(g);


			min = new int[n];
			Arrays.fill(min, INF);
			paintRed(0);

			int type;
			for (int i = 0; i < q; ++i) {
				type = in.nextInt();
				if (type == 1) {
					paintRed(in.nextInt() - 1);
				} else {
					out.println(query(in.nextInt() - 1));
				}
			}


			in.close();
			System.err.println("Time: " + (System.currentTimeMillis() - startTime) + " miliseconds");
		}

	}

	static class Graphs {
		public static int[][] buildParent(int[] par, int log) {
			int n = par.length;
			int[][] ret = new int[n][log];
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < log; ++j) {
					ret[i][j] = -1;
				}

			for (int i = 0; i < n; ++i) {
				ret[i][0] = par[i];
			}

			for (int j = 1; j < log; ++j) {
				for (int i = 0; i < n; ++i)
					if (ret[i][j - 1] != -1) {
						ret[i][j] = ret[ret[i][j - 1]][j - 1];
					}
			}
			return ret;
		}

		public static int[][] packU(int n, int[] from, int[] to) {
			int[][] g = new int[n][];
			int[] p = new int[n];
			for (int f : from)
				p[f]++;
			for (int t : to)
				p[t]++;
			for (int i = 0; i < n; i++)
				g[i] = new int[p[i]];
			for (int i = 0; i < from.length; i++) {
				g[from[i]][--p[from[i]]] = to[i];
				g[to[i]][--p[to[i]]] = from[i];
			}
			return g;
		}

		public static int[] buildCentroidTree(int[][] g) {
			int n = g.length;
			int[] ctpar = new int[n];
			Arrays.fill(ctpar, -1);
			buildCentroidTree(g, 0, new boolean[n], new int[n], new int[n], new int[n], ctpar);
			return ctpar;
		}

		private static int buildCentroidTree(int[][] g, int root, boolean[] sed, int[] par, int[] ord, int[] des, int[] ctpar) {
			// parent and level-order
			ord[0] = root;
			par[root] = -1;
			int r = 1;
			for (int p = 0; p < r; p++) {
				int cur = ord[p];
				for (int nex : g[cur]) {
					if (par[cur] != nex && !sed[nex]) {
						ord[r++] = nex;
						par[nex] = cur;
					}
				}
			}
			// if(r == 1)return;

			// DP and find a separator
			int sep = -1; // always exists
			outer:
			for (int i = r - 1; i >= 0; i--) {
				int cur = ord[i];
				des[cur] = 1;
				for (int e : g[cur]) {
					if (par[cur] != e && !sed[e]) des[cur] += des[e];
				}
				if (r - des[cur] <= r / 2) {
					for (int e : g[cur]) {
						if (par[cur] != e && !sed[e] && des[e] >= r / 2 + 1) continue outer;
					}
					sep = cur;
					break;
				}
			}

			sed[sep] = true;
			for (int e : g[sep]) {
				if (!sed[e]) ctpar[buildCentroidTree(g, e, sed, par, ord, des, ctpar)] = sep;
			}
			return sep;
		}

	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public void close() {

		}

	}

	static class LCA2 {
		private int[][][] gw;
		private int[][] gw1;
		int[] p;
		int[][] par;
		int[] dep;
		int log = 1;

		public LCA2(int n, int root, int[][][] gw) {
			this.gw = gw;
			p = new int[n];
			dep = new int[n];
			dfs(root, -1);
			for (log = 1; (1 << log) < n; log++) ;
			//log++;
			par = Graphs.buildParent(p, log);

		}

		public LCA2(int n, int root, int[][] gw1) {
			this.gw1 = gw1;
			p = new int[n];
			dep = new int[n];
			dfs1(root, -1);
			for (log = 1; (1 << log) < n; log++) ;
			//log++;
			par = Graphs.buildParent(p, log);

		}

		public int getLCA(int a, int b) {
			if (dep[a] > dep[b]) return getLCA(b, a);
			for (int i = log - 1; i >= 0; i--) {
				if (par[b][i] != -1 && dep[par[b][i]] >= dep[a]) {
					b = par[b][i];
				}
			}
			if (a == b) return a;
			for (int i = log - 1; i >= 0; i--) {
				if (par[a][i] != par[b][i]) {
					a = par[a][i];
					b = par[b][i];
				}
			}
			return par[a][0];
		}

		private void dfs(int v, int par) {
			p[v] = par;
			if (par != -1) {
				dep[v] = dep[par] + 1;
			}
			for (int[] e : gw[v]) {
				int u = e[0];
				if (u != par) {
					dfs(u, v);
				}
			}
		}

		private void dfs1(int v, int par) {
			p[v] = par;
			if (par != -1) {
				dep[v] = dep[par] + 1;
			}
			for (int u : gw1[v]) {
				if (u != par) {
					dfs1(u, v);
				}
			}
		}

	}
}

