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
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;

public class E342 {
	InputStream is;
	PrintWriter out;
	int n;
	int q;
	int nn=0,Inf = (int) (1e9);
	int log;
	int L[];
	int P[][];
	int Par[];
	int sub[];
	int ans[];
	HashSet<Integer> a[];
	void solve() {
		n = ni();
		q = ni();
		log = (int) Math.ceil(Math.log10(n)/Math.log10(2));
		P = new int[n+1][log+1];
		L = new int[n+1];
		a = new HashSet[n+1];
		sub = new int[n+1];
		Par = new int[n+1];
		ans = new int[n+1];
		Arrays.fill(ans,Inf);
		for(int i=0;i<=n;i++)
			a[i] = new HashSet<>();
		for(int i=0;i<n-1;i++){
			int u = ni();
			int v = ni();
			a[u].add(v);
			a[v].add(u);
		}
		preprocess();
		decompose(1,-1);
		update(1);           //Initially first node is painted
		while(q-->0){
			int t = ni();
			if(t==1){
				update(ni());
			}else{
				out.println(query(ni()));
			}
		}
	}
	
	
	// query
	void update(int u){
		int x = u;
		while(true){
			ans[x] = min(ans[x],dist(x,u));
			if(Par[x]==x)
				break;
			x = Par[x];
		}
	}
	
	int query(int u){
		int x=u,ret=Inf;
		while(true){
			ret = min(ret,ans[x]+dist(x,u));
			if(Par[x]==x)
				break;
			x = Par[x];
		}
		return ret;
	}
	
	// centorid decomposition
	void decompose(int root,int p){
		nn = 0;
		dfs1(root,root);
		int centroid = dfs2(root,root);
		if(p==-1)
			p = centroid;
		Par[centroid] = p;
		for(int k:a[centroid]){
			a[k].remove(centroid);
			decompose(k,centroid);
		}
		a[centroid].clear();
	}
	
	int dfs2(int c,int p){
		for(int k:a[c]){
			if(k!=p && sub[k]>nn/2){
				return dfs2(k,c);
			}
		}
		return c;
	}
	
	void dfs1(int c,int p){
		nn++;
		sub[c]=1;
		for(int k:a[c]){
			if(k!=p){
				dfs1(k,c);
				sub[c]+=sub[k];
			}
		}
	}
	
	// find distance between two node
	void preprocess(){
		dfs(1,-1);
		for(int i=1;i<=log;i++){	
			for(int j=1;j<=n;j++)
				P[j][i] = P[P[j][i-1]][i-1];
		}
	}
	void dfs(int node, int p) {
		if(p!=-1){
			P[node][0] = p;
			L[node] = L[p] + 1;
		}
		for (int k : a[node]) {
			if (k != p)
				dfs(k, node);
		}
	}
	int dist(int u,int v){
		return L[u]+L[v]-2*L[lca(u,v)];
	}
	
	int lca(int u, int v) {
		if(L[u]>L[v]){
			int temp = u;
			u = v;
			v = temp;
		}
		for(int i=log;i>=0;i--){
			if((1<<i)<=L[v]-L[u])				//make both node's level same
				v = P[v][i];
		}
		if(u==v)
			return u;
		for(int i=log;i>=0;i--){
			if(P[u][i]!=P[v][i])   				//shift up both u and v
			{
				u = P[u][i];
				v = P[v][i];
			}
		}
		return P[u][0];
	}

	int min(int a,int b){
		return (int)Math.min(a,b);
	}
	
	void run() throws Exception {
		String INPUT = "/media/sagar407/D/java workspace/11Input_output/input.txt";
		is = oj ? System.in : new FileInputStream(INPUT);
		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 Thread(null, new Runnable() {
			public void run() {
				try {
					new E342().run();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	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 boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}
