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 E implements Runnable{
	public static void main (String[] args) {new Thread(null, new E(), "_cf", 1 << 28).start();}

	int n, t = 1;
	boolean[] cent;
	int[][] adj, cadj;
	int[] size, arr, time, depth, when;
	
	public void run() {
//		try { new TestGenerator(); } catch (Exception e) {}
		FastScanner fs = new FastScanner();
//		try { fs = new FastScanner("testdata.out"); } catch (Exception e) {}
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		long start = System.nanoTime();
		
		n = fs.nextInt();
		int q = fs.nextInt();
		readTree(fs);
		
		time = new int[n]; Arrays.fill(time, -1);
		cent = new boolean[n];
		size = new int[n];
		arr = new int[n];
		cadj = new int[n][];
		depth = new int[n];
		when = new int[n];
		int centr = decomp(0);
		
		int log = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)*2);
		int[][] lift = new int[log][n];
		for(int[] d : lift) Arrays.fill(d, -1);
		int tailQ = 0;
		time[tailQ++] = 0;
		for(int i = 0; i < tailQ; i++) {
			int u = time[i];
			for(int v : adj[u]) {
				if(lift[0][u] == v) continue;
				lift[0][v] = u;
				depth[v] = depth[u] + 1;
				time[tailQ++] = v;
			}
		}

		for(int p = 1; p < log; p++) {
			for(int i = 0; i < n; i++) {
				int up = lift[p-1][i];
				if(up == -1) continue;
				lift[p][i] = lift[p-1][up];
			}
		}
		
		int[] tx = new int[n]; int mx = 0;
		Arrays.fill(arr, -1);
		tailQ = 0;
		time[tailQ++] = centr;
		for(int i = 0; i < tailQ; i++) {
			int u = time[i];
			mx = Math.max(mx, tx[u]);
			for(int v : cadj[u]) {
				if(v == arr[u]) continue;
				arr[v] = u;
				tx[v] = tx[u]+1;
				time[tailQ++] = v;
			}
		}
		
		int[] dist = new int[n];
		Arrays.fill(dist, 3*n);
		int at = 0;
		while(at != -1) {
			dist[at] = Math.min(dist[at], dist(at, 0, lift));
			at = arr[at];
		}
		while(q-->0) {
			int type = fs.nextInt();
			int u = fs.nextInt()-1;
			if(type == 1) {
				at = u;
				while(at != -1) {
					dist[at] = Math.min(dist[at], dist(at, u, lift));
					at = arr[at];
				}
				
			}
			else {
				int res = 3*n;
				at = u;
				while(at != -1) {
					res = Math.min(res, dist[at] + dist(at, u, lift));
					at = arr[at];
				}
				out.println(res);
			}
		}
		
		out.close();
	}
	
	int dist(int u, int v, int[][] lift) {
		int lca = lca(u, v, lift);
		return depth[u] + depth[v] - 2 * depth[lca];
	}

	int lca(int u, int v, int[][] lift) {
		if(u == v) return u;
		if(depth[v] > depth[u]) return lca(v, u, lift);
		int log = lift.length;
		for(int i = log - 1; i >= 0; i--) {
			if(lift[i][u] == -1) continue;
			if(depth[lift[i][u]] >= depth[v]) {
				u = lift[i][u];
			}
		}
		if(u == v) return u;
		for(int i = log-1; i >= 0; i--) {
			if(lift[i][u] != lift[i][v]) {
				u = lift[i][u];
				v = lift[i][v];
			}
		}
		return lift[0][v];
	}
	
	int decomp(int root) {
		int tailQ = 0;
		arr[tailQ++] = root;
		when[root] = t;
		for(int i = 0; i < tailQ; i++) {
			int u = arr[i];
			for(int v : adj[u]) {
				if(cent[v]) continue;
				if(v == time[u] && when[v] == t) continue;
				when[v] = t;
				time[v] = u;
				arr[tailQ++] = v;
			}
		}
		for(int i = tailQ-1; i >= 0; i--) {
			int u = arr[i];
			size[u] = 1;
			for(int v : adj[u]) {
				if(cent[v] || time[u] == v) continue;
				size[u] += size[v];
			}
		}
		int centr = -1;
		for(int i = 0; i < tailQ; i++) {
			int u = arr[i];
			boolean centroid = true;
			for(int v : adj[u]) {
				if(cent[v]) continue;
				if(v == time[u]) continue;
				centroid &= size[v] <= tailQ/2;
			}
			if(centroid && tailQ - size[u] <= tailQ/2 ) {
				centr = u;
				break;
			}
		}
		cent[centr] = true;
		int count = 0;
		for(int v : adj[centr]) 
			if(!cent[v]) count++;
		cadj[centr] = new int[count];
		count = 0;
		for(int v : adj[centr]) {
			if(cent[v]) continue;
			t++;
			int next = decomp(v);
			cadj[centr][count++] = next;
		}
		
		return centr;
	}
	
	void readTree(FastScanner fs) {
		adj = new int[n][];
		int[] deg = new int[n];
		int[][] es = new int[2][n-1];
		for(int i = 0; i < n - 1; i++) {
			int u = fs.nextInt()-1;
			int v = fs.nextInt()-1;
			es[0][i] = u; es[1][i] = v;
			deg[u]++; deg[v]++;
		}
		for(int i = 0; i < n; i++) adj[i] = new int[deg[i]];
		for(int i = 0; i < n - 1; i++) {
			int u = es[0][i];
			int v = es[1][i];
			adj[u][--deg[u]] = v;
			adj[v][--deg[v]] = u;
		}
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}