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.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Tester
{
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	ArrayList<Integer> tree[];
	
	void solve() {
		int n=ni();
		int m=ni();
		init(n);
		
		int u,v;
		for (int i=0;i<n-1;i++)
		{
			u=ni()-1;
			v=ni()-1;
			tree[u].add(v);
			tree[v].add(u);
		}
		LcaSparseTable lst=new LcaSparseTable(0);
		CentroidDecomposition cd=new CentroidDecomposition(n,0,lst);
		cd.update(0);
		
		while (m-->0)
		{
			int type=ni();
			u=ni()-1;
			if (type==1)
				cd.update(u);
			else
				out.println(cd.query(u));
		}
	}
	
	void init(int n)
	{
		tree=new ArrayList[n];
		for (int i=0;i<n;i++)
			tree[i]=new ArrayList<Integer>();
		
	}
	
	
	class CentroidDecomposition {
		int depth[], parent[];
		int inf = (int) (1e9);
		int center = -1, n;
		long ans[];
		LcaSparseTable lst;

		public CentroidDecomposition(int nn, int root,LcaSparseTable lt) {
			n = nn;
			depth = new int[n];
			parent = new int[n];
			ans = new long[n];
			Arrays.fill(depth, -1);
			Arrays.fill(ans, inf);
			lst = lt;
			findCentroid(root, n, -1, 0);
		}

		void findCentroid(int root, int size, int last, int h) {

			center = -1;
			dfs(root, -1, size);
			depth[center] = h;
			parent[center] = last;
			int cn = center;

			for (int u : tree[center])
				if (depth[u] == -1)
					findCentroid(u, size / 2, cn, h + 1);
		}

		int dfs(int v, int p, int n) {

			int cnt = 1;
			for (int u : tree[v])
				if (u != p && depth[u] == -1)
					cnt += dfs(u, v, n);

			if (center == -1 && (cnt * 2 >= n || p == -1))
				center = v;

			return cnt;
		}

		void update(int v) {
			int u = v;
			while (u != -1) {
				ans[u] = Math.min(ans[u], lst.dist(u, v));
				u = parent[u];
			}
		}

		long query(int v) {
			long res = ans[v];
			int u = v;
			while (u != -1) {
				res = Math.min(res, ans[u] + lst.dist(u, v));
				u = parent[u];
			}
			return res;
		}
	}
	class LcaSparseTable {

		int len;
		int[][] up;
		int[] tin;
		int[] tout;
		int time;
		long d[];

		void dfs(int u, int p) {
			tin[u] = time++;
			up[0][u] = p;
			for (int i = 1; i < len; i++)
				up[i][u] = up[i - 1][up[i - 1][u]];
			for (int v : tree[u])
				if (v != p)
					dfs(v, u);
			tout[u] = time++;
		}

		public LcaSparseTable(int root) {
			int n = tree.length;
			len = 1;
			while ((1 << len) <= n)
				++len;
			up = new int[len][n];
			tin = new int[n];
			tout = new int[n];
			dfs(root, root);
			d = new long[n];
			dfs2(root, root, 0);
		}

		boolean isParent(int parent, int child) {
			return tin[parent] <= tin[child] && tout[child] <= tout[parent];
		}

		public int lca(int a, int b) {
			if (isParent(a, b))
				return a;
			if (isParent(b, a))
				return b;
			for (int i = len - 1; i >= 0; i--)
				if (!isParent(up[i][a], b))
					a = up[i][a];
			return up[0][a];
		}

		void dfs2(int x, int p, int dist) {
			d[x] = dist;
			for (int nei : tree[x]) {
				if (nei != p) {
					dfs2(nei, x, dist + 1);
				}
			}
		}

		long dist(int x, int y) {
			return d[x] + d[y] - 2 * d[lca(x, y)];
		}
	}	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception 
	{ new Tester().run(); }
	
	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 static void tr(Object... o) 
	{ System.out.println(Arrays.deepToString(o)); }
}