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 Main {

	BufferedReader in;
	StringTokenizer str = null;
	PrintWriter out;
	
	private String next() throws Exception{
		while (str == null || !str.hasMoreElements())
			str = new StringTokenizer(in.readLine());
		return str.nextToken();
	}
	
	private int nextInt() throws Exception{
		return Integer.parseInt(next());
	}
	
	private long nextLong() throws Exception{
		return Long.parseLong(next());
	}
	
	private double nextDouble() throws Exception{
		return Double.parseDouble(next());
	}

	final int oo = Integer.MAX_VALUE / 2;
	
    int n;
    List<Integer> []g;
	int [][]up;

	final int LOG = 21;
	int []tin, tout, d;
	int tick = 0;

	boolean []deleted;
	int []size;
	int []parent, ans;

	public void run() throws Exception{
		in =  new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
    	n = nextInt();
		int Q = nextInt();
		g = new LinkedList[n];
		for(int i = 0; i < n; ++i) {
			g[i] = new LinkedList<Integer>();
		}
		for(int i = 0; i < n - 1; ++i) {
			int u = nextInt() - 1, v = nextInt() - 1;
			g[v].add(u);
			g[u].add(v);
		}

		up = new int[LOG][n];
		tin = new int[n];
		tout = new int[n];
		d = new int[n];

		dfs(0, -1);

		size = new int[n];
		deleted = new boolean[n];
		parent = new int[n];
		ans = new int[n];
		Arrays.fill(ans, oo);

		decompose(0, -1);
        // System.out.println(Arrays.toString(parent));

		update(0);
		while(Q-->0) {
			int type = nextInt(), v = nextInt() - 1;
			if (type == 1) update(v);
			else out.println(query(v));
            // System.out.println(Arrays.toString(ans));
		}

		out.close();
	}

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

	private int query(int v) {
		int cur = v, min = oo;
		while(cur != -1) {
			min = Math.min(min, ans[cur] + dist(cur, v));
			cur = parent[cur];
		}
		return min;
	}

	private int decompose(int v, int p) {
		int centroid = centroid(v, p);	
		deleted[centroid] = true;
        for(int i : g[centroid]) {
			if (p == i || deleted[i]) continue;
            int other = decompose(i, centroid);
			parent[other] = centroid;
		}
		
		parent[centroid] = -1;
		return centroid;
	}

	private int centroid(int v, int p) {
		// Arrays.fill(size, -1);
        dfs2(v, p);	
        // System.out.println("v = " + v + " p = " + p);
        // System.out.println(Arrays.toString(size));
		return findCentroid(v, p, size[v]);
	}

	private void dfs2(int v, int p) {
		size[v] = 1;
		for(int i : g[v]) {
			if (i == p || deleted[i]) continue;
			dfs2(i, v);
			size[v] += size[i];
		}
	}

	private int findCentroid(int v, int p, int N) {
		while(true) {
			boolean isCentroid = true;
			for(int i : g[v]) {
				if (i == p || deleted[i]) continue;
				if (size[i] * 2 > N) {
					p = v;
					v = i;
					isCentroid = false;
					break;
				}
			}	
			if (isCentroid) {
				return v;
			}
		}
	}

	private void dfs(int v, int p) {
		tin[v] = ++tick;
		
		if (p == -1) up[0][v] = v;	
		else {
			up[0][v] = p;
			d[v] = d[p] + 1;
		}

		for(int i = 1; i < LOG; ++i) {
			up[i][v] = up[i - 1][up[i - 1][v]];
		}

		for(int i : g[v]) {
			if (i == p) continue;
			dfs(i, v);
		}
		tout[v] = ++tick;
	}

	private boolean upper(int a, int b) {
		return tin[a] <= tin[b] && tout[b] <= tout[a];
	}

	private int lca(int a, int b) {
		if (upper(a, b)) return a;
		if (upper(b, a)) return b;
		for(int i = LOG - 1; i >= 0; --i) {
			if (!upper(up[i][a], b)) {
				a = up[i][a];
			}
		}
		return up[0][a];
	}

	private int dist(int a, int b) {
		int lca = lca(a, b);
		return d[a] + d[b] - 2 * d[lca];
	}
		
	public static void main(String[] args) throws Exception{
		new Main().run();
	}
}
