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.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;

public class XeniaAndTree {
	static final int oo = Integer.MAX_VALUE / 2;

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner(System.in);
		FastPrinter out = new FastPrinter(System.out);
		run(sc, out);
		out.close();
	}

	public static void run(FastScanner sc, FastPrinter out) throws Exception {
		int N = sc.nextInt();
		int M = N - 1;
		int Q = sc.nextInt();
		ArrayList<Integer>[] adj = new ArrayList[N];
		boolean[] centroid = new boolean[N];
		for (int i = 0; i < N; i++) {
			adj[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
		Node root = centroidDecomp(0, adj, centroid, new int[N], null);
		Node[] nodes = new Node[N];
		root.addToArray(nodes);
		nodes[0].update(0);
		for (int q = 0; q < Q; q++) {
			int t = sc.nextInt();
			int v = sc.nextInt() - 1;
			if (t == 1) {
				nodes[v].update(v);
			} else if (t == 2) {
				out.println(nodes[v].query(v));
			}
		}
	}

	private static Node centroidDecomp(int node, ArrayList<Integer>[] adj, boolean[] isCentroid, int[] size, Node parent) {
		// dfs for size info
		computeSubTreeSizes(node, adj, isCentroid, size, -1);
		int centroid = findCentroid(node, adj, isCentroid, size, size[node], -1);
		int numForests = 0;
		for (int child : adj[centroid]) {
			if (!isCentroid[child]) {
				numForests++;
			}
		}
		Node cur = new Node(centroid, parent, numForests);
		getDists(cur, centroid, -1, 0, adj, isCentroid);
		numForests = 0;
		isCentroid[centroid] = true;
		for (int child : adj[centroid]) {
			if (!isCentroid[child]) {
				cur.children[numForests++] = centroidDecomp(child, adj, isCentroid, size, cur);
			}
		}
		return cur;
	}

	private static void getDists(Node centroid, int node, int parent, int depth, ArrayList<Integer>[] adj, boolean[] isCentroid) {
		centroid.dists.put(node, depth);
		for (int child : adj[node]) {
			if (child != parent && !isCentroid[child]) {
				getDists(centroid, child, node, depth + 1, adj, isCentroid);
			}
		}

	}

	static class Node {
		int id;
		int ans;
		Node parent;
		Node[] children;
		HashMap<Integer, Integer> dists;

		public Node(int id, Node parent, int numChildren) {
			super();
			this.id = id;
			this.parent = parent;
			this.children = new Node[numChildren];
			dists = new HashMap<>();
			ans = oo;
		}

		public void update(int node) {
			int dist = dists.get(node);
			if (dist < ans) ans = dist;
			if (parent != null) {
				parent.update(node);
			}
		}

		public int query(int node) {
			int dist = ans + dists.get(node);
			if (parent != null) {
				int temp = parent.query(node);
				if (temp < dist) dist = temp;
			}
			return dist;
		}

		public void addToArray(Node[] nodes) {
			nodes[id] = this;
			for (Node child : children) {
				child.addToArray(nodes);
			}
		}
	}

	private static int findCentroid(int node, ArrayList<Integer>[] adj, boolean[] isCentroid, int[] size, int totSize, int parent) {
		int centroid = -1;
		for (int child : adj[node]) {
			if (child != parent && !isCentroid[child]) {
				if (size[child] > totSize / 2) {
					centroid = findCentroid(child, adj, isCentroid, size, totSize, node);
					break;
				}
			}
		}
		if (centroid == -1) centroid = node;
		return centroid;
	}

	private static void computeSubTreeSizes(int node, ArrayList<Integer>[] adj, boolean[] centroid, int[] size, int parent) {
		size[node] = 1;
		for (int child : adj[node]) {
			if (child != parent && !centroid[child]) {
				computeSubTreeSizes(child, adj, centroid, size, node);
				size[node] += size[child];
			}
		}
	}

	static class FastPrinter {
		StringBuilder buf;
		PrintWriter pw;

		public FastPrinter(OutputStream stream) {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
		}

		public FastPrinter(String fileName) throws Exception {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
		}

		public void print(int a) {
			buf.append(a);
		}

		public void print(long a) {
			buf.append(a);
		}

		public void print(char a) {
			buf.append(a);
		}

		public void print(char[] a) {
			buf.append(a);
		}

		public void print(double a) {
			buf.append(a);
		}

		public void print(String a) {
			buf.append(a);
		}

		public void print(Object a) {
			buf.append(a.toString());
		}

		public void println() {
			buf.append('\n');
		}

		public void println(int a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(long a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(char a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(char[] a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(double a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(String a) {
			buf.append(a);
			buf.append('\n');
		}

		public void println(Object a) {
			buf.append(a.toString());
			buf.append('\n');
		}

		public void close() {
			pw.print(buf);
			pw.close();
		}

	}

	static class FastScanner {
		final private int BUFFER_SIZE = 1 << 20;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public FastScanner(InputStream stream) {
			din = new DataInputStream(stream);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastScanner(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		int[] nextIntArray(int N) throws IOException {
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		String nextLine() throws IOException {
			int c = read();
			while (c != -1 && isEndline(c))
				c = read();
			if (c == -1) {
				return null;
			}
			StringBuilder res = new StringBuilder();
			do {
				if (c >= 0) {
					res.appendCodePoint(c);
				}
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

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

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

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

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg) return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg) return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg) return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1) buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead) fillBuffer();
			return buffer[bufferPointer++];
		}

		private int readOutSpaces() throws IOException {
			while (true) {
				if (bufferPointer == bytesRead) fillBuffer();
				int c = buffer[bufferPointer++];
				if (!isSpaceChar(c)) {
					return c;
				}
			}
		}

		public void close() throws IOException {
			if (din == null) return;
			din.close();
		}
	}

}