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 CF342E {
	class Tree {
		int n, lg;
		int[] depth, best, p, cnt, subtree;
		int[][] adj, cc, lift;
		boolean[] used;
		public Tree(int nn, int[][] input) {
			adj = new int[n = nn][];
			cnt = new int[n];
			for(int i = 0 ; i < n - 1 ; i++) {
				cnt[input[0][i]]++;
				cnt[input[1][i]]++;
			}
			for(int i = 0 ; i < n ; i++)
				adj[i] = new int[cnt[i]];
			for(int i = 0 ; i < n - 1 ; i++)
				add(input[0][i], input[1][i]);
			lg = 32 - Integer.numberOfLeadingZeros(n);
			subtree = new int[n];
			p = new int[n];
			depth = new int[n];
			used = new boolean[n];
			best = new int[n];
			Arrays.fill(best, (int) 1e9);
			cc = new int[lg][n];
			lift = new int[lg][n];
			for(int k = 0 ; k < lg ; k++) {
				Arrays.fill(lift[k], -1);
				Arrays.fill(cc[k], -1);
			}
			build();
			go(0, 0);
		}
		void add(int u, int v) {
			adj[u][--cnt[u]] = v;
			adj[v][--cnt[v]] = u;
		}
		void calcSub(int u, int par) {
			p[u] = par;
			subtree[u] = 1;
			for(int v : adj[u]) {
				if(v != p[u] && !used[v]) {
					calcSub(v, u);
					subtree[u] += subtree[v];
				}
			}
		}
		int findCentroid(int first) {
			calcSub(first, first);
			Deque<Integer> q = new ArrayDeque<>();
			q.add(first);
			int centroid = -1;
			while(!q.isEmpty()) {
				int u = q.pop();
				int maxSize = subtree[first] - subtree[u];
				for(int v : adj[u]) {
					if(p[u] != v && !used[v]) {
						maxSize = Math.max(maxSize, subtree[v]);
						q.add(v);
					}
				}
				if(maxSize <= subtree[first] / 2) {
					centroid = u;
					break;
				}
			}
			return centroid;
		}
		void go(int ep, int lvl) {
			int centroid = findCentroid(ep);
			solveTree(centroid, lvl);
			used[centroid] = true;
			for(int v : adj[centroid]) if(!used[v]) go(v, lvl + 1);
		}
		void solveTree(int centroid, int lvl) {
			Deque<Integer> q = new ArrayDeque<>();
			q.addLast(centroid); q.add(-1);
			while(!q.isEmpty()) {
				int u = q.pop(), prev = q.pop();
				cc[lvl][u] = centroid;
				for(int v : adj[u]) {
					if(v != prev && !used[v]) {
						q.add(v);
						q.add(u);
					}
				}
			}
		}
		void build() {
			Deque<Integer> q = new ArrayDeque<>();
			q.add(0);
			while(!q.isEmpty()) {
				int u = q.pop();
				for(int v : adj[u]) {
					if(lift[0][u] != v) {
						lift[0][v] = u;
						depth[v] = depth[u] + 1;
						q.add(v);
					}
				}
			}
			for(int k = 1 ; k < lg ; k++)
				for(int i = 0 ; i < n ; i++)
					if(lift[k - 1][i] != -1)
						lift[k][i] = lift[k - 1][lift[k - 1][i]];
		}
		int dist(int u, int v) { return depth[u] + depth[v] - (depth[lca(u, v)] << 1); }
		int walk(int u, int w) {
			for(int k = 0 ; k < lg ; k++)
				if((w & (1 << k)) > 0)
					u = lift[k][u];
			return u;
		}
		int lca(int u, int v) {
			if(depth[v] > depth[u]) return lca(v, u);
			u = walk(u, depth[u] - depth[v]);
			if(u == v) return u;
			for(int k = lg - 1 ; k >= 0 ; k--) {
				if(lift[k][u] != lift[k][v]) {
					u = lift[k][u];
					v = lift[k][v];
				}
			}
			return lift[0][u];
		}
		void update(int x) { // lg(n)^2
			for(int lvl = lg - 1 ; lvl >= 0 ; lvl--)
				if(cc[lvl][x] != -1)
					best[cc[lvl][x]] = Math.min(best[cc[lvl][x]], dist(x, cc[lvl][x]));
		}
		int query(int x) { // lg(n)^2
			int res = Integer.MAX_VALUE;
			for(int lvl = lg - 1 ; lvl >= 0 ; lvl--)
				if(cc[lvl][x] != -1)
					res = Math.min(res, dist(x, cc[lvl][x]) + best[cc[lvl][x]]);
			return res;
		}
	}
	public CF342E() {
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt(), q = scan.nextInt();
		int[][] edges = new int[2][n - 1];
		for(int i = 0 ; i < n - 1 ; i++) {
			edges[0][i] = scan.nextInt() - 1;
			edges[1][i] = scan.nextInt() - 1;
		}
		Tree t = new Tree(n, edges);
//		for(int lvl = 0 ; lvl < t.lg ; lvl++) {
//			System.out.printf("Lvl: %d: ", lvl);
//			for(int i = 0 ; i < t.n ; i++) {
//				System.out.printf("%2d", t.cc[lvl][i]);
//			}
//			System.out.println();
//		}
		t.update(0);
		for(int qq = 0 ; qq < q ; qq++) {
			int type = scan.nextInt(), x = scan.nextInt() - 1;
			if(type == 1) t.update(x);
			else out.println(t.query(x));
		}
		out.close();
	}	
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF342E(); }
}