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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner input = new FastScanner(System.in);
		
		int N = input.nextInt();
		int Q = input.nextInt();
		
		LinkedList<Integer>[] adj = new LinkedList[N];
		for (int i = 0; i < N; i++)
			adj[i] = new LinkedList<>();
		
		for (int i = 0; i < N - 1; i++) {
			int x = input.nextInt() - 1;
			int y = input.nextInt() - 1;
			adj[x].add(y); adj[y].add(x);
		}
		
		CentroidDecomposition graph = new CentroidDecomposition(adj);
		graph.activate(0);
		
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for (int q = 0; q < Q; q++)
			if (input.nextInt() == 1) graph.activate(input.nextInt() - 1);
			else out.append(graph.getmin(input.nextInt() - 1) + "\n");
		
		out.close();
	}
	
	static class CentroidDecomposition {
		
		int N;
		int[] parent;
		int[] depth;
		int[][] dist;
		int[] best;
		
		LinkedList<Integer>[] adj;
		
		CentroidDecomposition(LinkedList<Integer>[] adj) {
			int N = adj.length;
			this.adj = adj;
			parent = new int[N]; depth = new int[N];
			Arrays.fill(parent, -1);
			dist = new int[N][(int) (Math.log(N) / Math.log(2)) + 1];
			best = new int[N];
			Arrays.fill(best, Integer.MAX_VALUE);
			centroid(0, 0, new boolean[N], new boolean[N], new int[N], -1);
		}
		
		void activate(int i) {
			int j = i;
			int l = depth[i];
			while (j != -1) {
				best[j] = Math.min(best[j], dist[i][l]);
				l--; j = parent[j];
			}
		}
		
		long getmin(int i) {
			int j = i; int l = depth[i];
			long min = Integer.MAX_VALUE;
			while (j != -1) {
				min = Math.min(min, (long) best[j] + dist[i][l]);
				l--; j = parent[j];
			}
			return min;
		}
		
		void centroid(int i, int layer, boolean[] visited, boolean[] marked, int[] subtree, int last) {
			obtainSubsz(i, visited, marked, subtree);
			int centroid = centroid(i, visited, marked, subtree, subtree[i]);
			parent[centroid] = last;
			dfs(layer, centroid, visited, marked, 0);
			marked[centroid] = true;
			depth[centroid] = layer;
			for (int w : adj[centroid])
				if (!marked[w])
					centroid(w, layer + 1, visited, marked, subtree, centroid);
		}
		
		void dfs(int l, int i, boolean[] visited, boolean[] marked, int d) {
			dist[i][l] = d;
			visited[i] = true;
			for (int w : adj[i])
				if (!visited[w] && !marked[w])
					dfs(l, w, visited, marked, d + 1);
			visited[i] = false;
		}
		
		int obtainSubsz(int i, boolean[] visited, boolean[] marked, int[] subtree) {
			subtree[i] = 1;
			visited[i] = true;
			for (int w : adj[i])
				if (!visited[w] && !marked[w])
					subtree[i] += obtainSubsz(w, visited, marked, subtree);
			visited[i] = false;
			return subtree[i];
		}
		
		int centroid(int i, boolean[] visited, boolean[] marked, int[] subtree, int n) { 
			int large = -1;
			
			visited[i] = true;
			for (int w : adj[i])
				if (!visited[w] && !marked[w])
					if (large == -1 || subtree[large] < subtree[w])
						large = w;
			
			if ((large == -1 || subtree[large] <= n / 2) && n - subtree[i] <= n / 2)
				return i;
			
			int centroid = centroid(large, visited, marked, subtree, n);
			visited[i] = false;
			return centroid;
		}
	}

	
	// Matt Fontaine's Fast IO
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

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

		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++];
		}

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

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

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

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