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
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;


public class Tester {
	
	InputStream in;
	PrintWriter out;
	
	int MAXB;
	int buffer[];
	int tin[],tout[],depth[],parent[],up[][],dis[];
	int len;
	int time;
	int cnt;
	int n;
	int c;
	ArrayList<Integer> g[];
	
	void init()
	{
		len = 1;
		while ((1 << len) <= n)
			++len;
		
		MAXB=(int) Math.sqrt(n);
		buffer=new int[MAXB];
		tin=new int[n];
		tout=new int[n];
		depth=new int[n];
		up = new int[len][n];
		dis = new int[n];
		Arrays.fill(dis, Integer.MAX_VALUE);
		g=new ArrayList[n];
		for (int i=0;i<n;i++)
			g[i]=new ArrayList<Integer>();
	}

	void dfs(int u, int p, int level) {
		depth[u] = level;
		dis[u]=depth[u];
		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 : g[u])
			if (v != p)
				dfs(v, u, level + 1);
		tout[u] = time++;
	}

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

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

	int distance(int a, int b) {
		return depth[a] + depth[b] - 2 * depth[lca(a, b)];
	}
	
	void bfs()
	{
		Queue<Integer> q=new LinkedList<Integer>();
		for (int i=0;i<c;i++)
		{
			q.add(buffer[i]);
			dis[buffer[i]]=0;
		}
		
		while (!q.isEmpty())
		{
			int u=q.remove();
			
			for (int v : g[u])
				if (dis[v]>dis[u]+1)
				{
					dis[v]=dis[u]+1;
					q.add(v);
				}
		}
	}
	
	void solve() 
	{
		n=ni();
		int m=ni();
		init();
		
		for (int i=0;i<n-1;i++)
		{
			int a=ni()-1;
			int b=ni()-1;
			g[a].add(b);
			g[b].add(a);
		}
		
		dfs(0,0,0);
		c=0;
		
		while (m-->0)
		{
			int t=ni();
			int u=ni()-1;
			
			if (t==1)
			{
				buffer[c++]=u;
			}
			else
			{
				int ans=dis[u];
				
				for (int i=0;i<c;i++)
					ans=Math.min(ans, distance(u, buffer[i]));
				
				out.println(ans);
			}
			
			if (c>=MAXB)
			{
				bfs();
				c=0;
			}
		}
		
	}
	
	
	void run() throws Exception {
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		//oj=true;
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		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 = in.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() {
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(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 (!(inSpaceChar(b))) { // when nextLine, (inSpaceChar(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 && !(inSpaceChar(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));
	}
	
}
