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

public class utkarsh {

	InputStream is;
	PrintWriter out;

	int dp[][], level[];

	void dfs0(int s, int p) {
		for(int x : a[s]) {
			if(x != p) {
				dp[0][x] = s;
				level[x] = level[s] + 1;
				dfs0(x, s);
			}
		}
	}

	void preprocess() {
		level = new int[n];
		dp = new int[logn][n];

		dfs0(0, -1);
		for(int i = 1; i < logn; i++) {
			for(int j = 0; j < n; j++) {
				dp[i][j] = dp[i-1][dp[i-1][j]];
			}
		}
	}

	int lca(int u, int v) {
		if(level[u] > level[v]) {
			u ^= v;	v ^= u;	u ^= v;
		}
		int d = level[v] - level[u];
		for(int i = 0; i < logn; i++) {
			if((d & (1 << i)) > 0)	v = dp[i][v];
		}
		if(u == v)	return u;
		for(int i = logn-1; i >= 0; i--) {
			if(dp[i][u] != dp[i][v]) {
				u = dp[i][u];
				v = dp[i][v];
			}
		}
		return dp[0][u];
	}

	int dist(int u, int v) {
		return level[u] + level[v] - 2 * level[lca(u, v)];
	}

	//----------------------------------------------------------

	int nn;
	int sub[], pt[];

	void dfs1(int s, int p) {
		sub[s] = 1;
		nn++;
		for(int x : a[s]) {
			if(x != p) {
				dfs1(x, s);
				sub[s] += sub[x];
			}
		}
	}

	int dfs2(int s, int p) {
		for(int x : a[s]) {
			if(x != p && sub[x] > nn / 2) {
				return dfs2(x, s);
			}
		}
		return s;
	}

	void decompose(int s, int p) {
		nn = 0;
		dfs1(s, -1);
		int centroid = dfs2(s, -1);
		if(p == -1)	p = centroid;
		pt[centroid] = p;
		for(int x : a[centroid]) {
			a[x].remove(centroid);
			decompose(x, centroid);
		}
		a[centroid].clear();
	}

	//----------------------------------------------------------

	int ans[], maxi = (int)2e9;

	void update(int u) {
		int x = u;
		ans[u] = 0;
		while(x != pt[x]) {
			x = pt[x];
			ans[x] = Math.min(ans[x], dist(x, u));
		}
	}

	int query(int u) {
		int x = u;
		int r = ans[u];
		while(x != pt[x]) {
			x = pt[x];
			r = Math.min(r, ans[x] + dist(x, u));
		}
		return r;
	}

	//----------------------------------------------------------

	HashSet<Integer> a[];
	int n, logn;

	void solve() {
		n = ni();

		logn = 20;

		int m = ni();
		a = new HashSet[n];
		for(int i = 0; i < n; i++)	a[i] = new HashSet<Integer>();
		for(int i = 1; i < n; i++) {
			int u = ni() - 1;
			int v = ni() - 1;
			a[u].add(v);
			a[v].add(u);
		}

		preprocess();	//for LCA

		sub = new int[n];
		pt = new int[n];
		decompose(0, -1);	// for centroid decomposition

		ans = new int[n];
		Arrays.fill(ans, maxi);

		update(0);

		while(m-- > 0) {
			int t = ni();
			int u = ni() - 1;
			if(t == 1) {
				update(u);
			} else {
				out.println(query(u));
			}
		}
	}
	//-----------------------------------------------------------

	void run() { 
        is = System.in; 
        out = new PrintWriter(System.out); 

        solve(); 
        out.flush();
    }
    public static void main(String[] args) { 
        new utkarsh().run();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); }
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0){ return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { 
        return !( c >= 33 && c <= 126 ); 
    }
    int skip(){ 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    int ni() { 
        int n = 0, b = readByte(); boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
}