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.*;
import java.math.*;
import java.security.KeyStore.Entry;
import java.util.*;

public class TestClass {
	private InputStream is;
	private PrintWriter out;

	ArrayList<Integer> a[];
	int p[][], level[], parent[], n;

	public void CL() {
		Queue<Integer> lp = new LinkedList<Integer>();
		lp.add(0);
		level[0] = 0;
		parent[0] = 0;
		boolean u[] = new boolean[a.length];
		while (!lp.isEmpty()) {
			int q = lp.poll();
			u[q] = true;
			for (int i = 0; i < a[q].size(); i++) {
				if (!u[a[q].get(i)])
					lp.add(a[q].get(i));
				else {
					level[q] = level[a[q].get(i)] + 1;
					parent[q] = a[q].get(i);
				}
			}
		}
	}

	public void BLCA() {
		for (int i = 0; i < n; i++)
			p[i][0] = parent[i];
		for (int j = 1; 1 << j < n; j++) {
			for (int i = 0; i < n; i++)
				p[i][j] = p[p[i][j - 1]][j - 1];
		}
	}

	public int dis(int x, int y) {
		if (level[x] < level[y]) {
			int t = x;
			x = y;
			y = t;
		}
		int log = 0, temp = level[x];
		while (temp != 0) {
			log++;
			temp >>= 1;
		}
		int di = 0;
		for (int i = log; i >= 0; i--) {
			if (level[x] - level[y] >= dp[i]) {
				di += dp[i];
				x = p[x][i];
			}
		}
		if (x == y)
			return di;
		for (int i = log; i >= 0; i--) {
			if (p[x][i] != p[y][i]) {
				x = p[x][i];
				y = p[y][i];
				di += 2 * (dp[i]);
			}
		}
		return di + 2;
	}

	int d[], dp[];
	TreeSet<Long> q = new TreeSet<Long>();
	public void bfs(boolean u[]) {
		while (!q.isEmpty()) {
			long nm = q.pollFirst();
			int no = (int) nm;
			int dis = (int) (nm >> 32);
			for (int i = 0; i < a[no].size(); i++) {
				if (d[a[no].get(i)] > dis + 1) {
					d[a[no].get(i)] = dis + 1;
					long mak = 0;
					mak = (((long) d[a[no].get(i)]) << 32) | (long) a[no].get(i);
					q.add(mak);
				}
			}
		}
	}

	private void soln() {
		n = ni();
		dp = new int[32];
		dp[0] = 1;
		for (int i = 1; i < 32; i++)
			dp[i] = dp[i - 1] * 2;
		int m = ni();
		a = new ArrayList[n];
		level = new int[n];
		parent = new int[n];
		d = new int[n];
		Arrays.fill(d, 1000000);
		p = new int[n][(int) (Math.log(n) / Math.log(2)) + 2];
		for (int i = 0; i < n; i++)
			a[i] = new ArrayList<Integer>();
		for (int i = 0; i < n - 1; i++) {
			int x = ni() - 1, y = ni() - 1;
			a[x].add(y);
			a[y].add(x);
		}
		CL();
		BLCA();
		boolean u[] = new boolean[n];
		u[0] = true;
		q.add((long)0);
		d[0] = 0;
		int cou = 0;
		int sq = (int) (Math.sqrt(m));
		while (cou != m) {
			bfs(u);
			ArrayList<Integer> te = new ArrayList<Integer>();
			for (int i = 0; i < sq; i++) {
				cou++;
				int t = ni(), no = ni() - 1;
				if (t == 1) {
					u[no] = true;
					d[no] = 0;
					q.add((long)no);
					te.add(no);
				} else {
					int fin = d[no];
					for (int j = 0; j < te.size(); j++)
						fin = Math.min(fin, dis(no, te.get(j)));
					System.out.println(fin);
				}
			}
		}
	}

	void run() throws Exception {
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		soln();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new TestClass().run();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}