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 javax.swing.plaf.synth.SynthSeparatorUI;

import java.io.*;

public class B {
	public static void main(String[] args) {
		new B().solve();
	}

	FasterScanner in = new FasterScanner();
	PrintWriter out = new PrintWriter(System.out);

	long mod = (long) 1e9 + 7;

	public void solve() {
		int n = in.nextInt();
		int m = in.nextInt();

		init(n);
		for (int i = 0; i < n - 1; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			g[a].add(b);
			g[b].add(a);
		}
		decompose(0, -1);
		
	//	for(int i=0;i<dist.length;i++) {
	//		System.out.println(Arrays.toString(dist[i]));
	//	}
	//	System.out.println("**********************");
	//	System.out.println(Arrays.toString(lastIdx));
	//	System.out.println(Arrays.toString(parent));
	//	System.out.println(Arrays.toString(dp));

		for (int i = 0; i < m; i++) {
			int t = in.nextInt();
			int v = in.nextInt() - 1;
			if (t == 1) {
				red[v] = true;
				updateUper(v);
			} else {
				out.println(giveAns(v));
			}
		}
		out.close();
	}

	static int giveAns(int x) {
		int ans = dp[x];
		int p = parent[x];
		int c = 0;
		while(p!=-1) {
			ans = Math.min(ans, dist[x][lastIdx[x]-c-1] + dp[p]);
			p = parent[p];
			c++;
		}
		return ans;
	}

	static void updateUper(int x) {
		dp[x] = 0;
		int p = parent[x];
		int c = 0;
		while (p != -1) {
			dp[p] = Math.min(dp[p], dist[x][lastIdx[x] - c - 1]);
			c++;
			p = parent[p];
		}
	}

	static void dfs1(int u, int p) {
		sub[u] = 1;
		nn++;
		for (int it : g[u])
			if (it != p) {
				dfs1(it, u);
				sub[u] += sub[it];
			}
	}

	static int dfs2(int u, int p) {
		for (int it : g[u])
			if (it != p && sub[it] > nn / 2)
				return dfs2(it, u);
		return u;
	}

	static void decompose(int root, int p) {
		nn = 0;
		dfs1(root, root);
		int centroid = dfs2(root, root);
	//	if (p == -1)
	//		p = centroid;
		parent[centroid] = p;
		dp[centroid] = MAX;
		if(red[centroid]) {
			dp[centroid] = 0;
		}
		for (int it : g[centroid]) {
			dp[centroid] = Math.min(dfs3(it, centroid, 1) + 1, dp[centroid]);		
		}
		for (int it : g[centroid]) {
			g[it].remove(centroid);
			decompose(it, centroid);
		}
		g[centroid].clear();
	}

	static int dfs3(int n, int p, int d) {
		int ans = MAX;
		if(red[n])
			ans = 0;
		dist[n][lastIdx[n]++] = d;
		for (int x : g[n]) {
			if (x != p) {
				ans = Math.min(ans, dfs3(x, n, d + 1) + 1);
			}
		}

		//System.out.println("DFS3 " + n +" "+ p + " "+ d+ " " + ans);
		return ans;
	}

	static boolean red[];
	static int[] dp;
	static TreeSet<Integer> g[];
	static int nn;
	static int MAX = Integer.MAX_VALUE / 2;
	static long res;
	static int[] sub;
	static int[] parent;
	static int[][] dist;
	static int[] lastIdx;

	static void init(int n) {
		res = 0;
		nn = 0;
		g = new TreeSet[n];
		for (int i = 0; i < n; i++) {
			g[i] = new TreeSet<Integer>();
		}
		sub = new int[n];
		parent = new int[n];
		dist = new int[n][(int) (2 * Math.log(n))];
		lastIdx = new int[n];
		dp = new int[n];
		red = new boolean[n];
		red[0] = true;
		
	}

	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

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

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

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

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long 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 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 double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		public int[] nextIntArray10(int n) {
			int[] arr = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray10(int n) {
			long[] arr = new long[n + 1];
			for (int i = 1; i <= n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		public int[] nextIntArray11(int n) {
			int[] arr = new int[n + 2];
			for (int i = 1; i <= n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray11(int n) {
			long[] arr = new long[n + 2];
			for (int i = 1; i <= n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}
	}

}