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.util.*;
import java.io.*;

public class p342E 
{
	static List<Integer>[] list;
	static int[] h, e, l, size, parent;
	static int index;
	static int[][] table;
	static boolean[] deleted;
	static int[] ans;
	static final int INF = (int)1e9;
	public static void main(String[] args) throws IOException 
	{
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer st = new StringTokenizer(f.readLine());
		int size = Integer.parseInt(st.nextToken());
		int queries = Integer.parseInt(st.nextToken());
		list = new LinkedList[size + 1];
		for(int i = 1; i <= size; i++)
			list[i] = new LinkedList<Integer>();
		for(int i = 0; i < size - 1; i++)
		{
			st = new StringTokenizer(f.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			list[u].add(v);
			list[v].add(u);
		}
		h = new int[size + 1];
		e = new int[2 * size - 1];
		l = new int[2 * size - 1];
		dfs(1, 0, -1);
		build(l);
		parent = new int[size + 1];
		p342E.size = new int[size + 1];
		deleted = new boolean[size + 1];
		decompose(1, -1, size);
		ans = new int[size + 1];
		Arrays.fill(ans, INF);
		update(1);
		while(queries-- > 0)
		{
			st = new StringTokenizer(f.readLine());
			int type = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken());
			if(type == 1)
				update(u);
			else
				out.println(query(u));
		}
		out.close();
	}
	
	public static int query(int v)
	{
		int result = INF;
		for(int u = v; u != -1; u = parent[u])
			result = Math.min(result, ans[u] + dist(u, v));
		return result;
	}
	
	public static void update(int v)
	{
		for(int u = v; u != -1; u = parent[u])
			ans[u] = Math.min(ans[u], dist(u, v));
	}
	
	public static void decompose(int u, int p, int vertices)
	{
		calcSizes(u, -1);
		int c = centroid(u, -1, vertices);
		parent[c] = p;
		deleted[c] = true;
		for(int v : list[c])
			if(!deleted[v])
				decompose(v, c, size[v]);
	}
	
	public static int centroid(int u, int p, int vertices)
	{
		outer:
		while(true)
		{
			for(int v : list[u])
			{
				if(v == p || deleted[v])
					continue;
				if(size[v] > vertices / 2)
				{
					p = u;
					u = v;
					continue outer;
				}
			}
			return u;
		}
	}
	
	public static int calcSizes(int u, int p)
	{
		size[u] = 1;
		for(int v : list[u])
			if(v != p && !deleted[v])
				size[u] += calcSizes(v, u);
		return size[u];
	}
	
	public static int dist(int u, int v)
	{
		return l[h[u]] + l[h[v]] - 2 * l[h[lca(u, v)]];
	}
	
	public static int lca(int u, int v)
	{
		if(h[u] < h[v])
			return e[rmq(h[u], h[v])];
		else
			return e[rmq(h[v], h[u])];
	}
	
	public static int rmq(int s, int e)
	{
		int k = lg(e - s + 1);
		if(l[table[k][s]] < l[table[k][e - (1 << k) + 1]])
			return table[k][s];
		return table[k][e - (1 << k) + 1];
	}
	
	public static void build(int[] a)
	{
		table = new int[lg(a.length) + 1][a.length];
		for(int c = 0; c < a.length; c++)
			table[0][c] = c;
		for(int r = 1; r < table.length; r++)
		{
			int flag = 1 << r - 1;
			for(int c = 0; c + flag < a.length; c++)
			{
				if(a[table[r - 1][c]] < a[table[r - 1][c + flag]])
					table[r][c] = table[r - 1][c];
				else
					table[r][c] = table[r - 1][c + flag];
			}
		}
	}
	
	public static int lg(int num)
	{
		return 31 - Integer.numberOfLeadingZeros(num);
	}
	
	public static void dfs(int u, int d, int p)
	{
		h[u] = index;
		e[index] = u;
		l[index] = d;
		index++;
		for(int v : list[u])
		{
			if(v == p)
				continue;
			dfs(v, d + 1, u);
			e[index] = u;
			l[index] = d;
			index++;
		}
	}
}