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.BufferedReader;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	
	static long totalCost = 0;
	static int[] size;
	static int[] level;
	static int[][] biDist;
	
	public static void main(String[] args) {
		InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solve(in, out);
        out.close();
	}
	
	private static void solve(InputReader in, PrintWriter out) {
		int n = in.nextInt();
		int m = in.nextInt();
		List<List<Integer>> g = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			g.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			g.get(a).add(b);
			g.get(b).add(a);
		}
		level = new int[n];
		size = new int[n];
		biDist = new int[20][n];
		CentroidNode[] centroids = new CentroidNode[n];
		decomposeTree(0, -1, g, centroids, 0);
		for (int i = 0; i < n; i++) {
			calculateDistance(i, g);
		}
		paint(0, 0, g, centroids);
		for (int i = 0; i < m; i++) {
			int t = in.nextInt();
			int node = in.nextInt() - 1;
			if (t == 1) {
				paint(node, node, g, centroids);
			} else {
				out.println(getClosest(node, node, g, centroids));
			}
		}
	}
	
	private static int getClosest(int node, int target, List<List<Integer>> g, CentroidNode[] centroids) {
		int ret = Integer.MAX_VALUE;
		while (node != -1) {
			CentroidNode currentNode = centroids[node];
			int currentDistance = currentNode.minDistance == Integer.MAX_VALUE ? Integer.MAX_VALUE : currentNode.minDistance + biDist[level[node]][target];
			ret = Math.min(currentDistance, ret);
			node = currentNode.parent;
		}
		return ret;
	}
	
	private static void paint(int node, int target, List<List<Integer>> g, CentroidNode[] centroids) {
		while (node != -1) {
			CentroidNode currentNode = centroids[node];
			currentNode.minDistance = Math.min(currentNode.minDistance, biDist[level[node]][target]);
			node = currentNode.parent;
		}
	}
	
	private static int decomposeTree(int node, int p, List<List<Integer>> g, CentroidNode[] centroids, int l) {
		int centroid = getCentroid(node, centroids, g);
		level[centroid] = l;
		List<Integer> children = new ArrayList<>();
		centroids[centroid] = new CentroidNode(p, children);
		for (int child : g.get(centroid)) {
			if (centroids[child] == null) {
				children.add(decomposeTree(child, centroid, g, centroids, l + 1));
			}
		}
		return centroid;
	}
	
	private static int getCentroid(int node, CentroidNode[] centroids, List<List<Integer>> g) {
		buildSumTree(node, -1, centroids, g);
		return getCentroid(node, -1, size[node], centroids, g);
	}
	
	private static int getCentroid(int node, int p, int n, CentroidNode[] centroids, List<List<Integer>> g) {
		int nextNode = 0;
		boolean centroid = true;
		for (int child : g.get(node)) {
			if (child == p || centroids[child] != null) {
				continue;
			}
			if (size[child] > n / 2) {
				centroid = false;
			}
			if (nextNode == 0 || size[child] > size[nextNode]) {
				nextNode = child;
			}
		}
		if (centroid && n - size[node] <= n/2) {
			return node;
		}
		return getCentroid(nextNode, node, n, centroids, g);
	}
	
	private static void buildSumTree(int node, int p, CentroidNode[] centroids, List<List<Integer>> g) {
		size[node] = 1;
		for (int child : g.get(node)) {
			if (child == p || centroids[child] != null) {
				continue;
			}
			buildSumTree(child, node, centroids, g);
			size[node] += size[child];
		}
	}
	
	private static int calculateDistance(int u, List<List<Integer>> g) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {u, -1});
		for (int dist = 0; !q.isEmpty(); dist++) {
			int size = q.size();
			while (size-- > 0) {
				int[] pair = q.poll();
				int node = pair[0];
				int p = pair[1];
				biDist[level[u]][node] = dist;
				List<Integer> neigs = g.get(node);
				for (int neig : neigs) {
					if (neig != p && level[neig] >= level[u]) {
						q.add(new int[] {neig, node});
					}
				}
			}
		}
		return 0;
	}
	
	static class CentroidNode {
		int parent;
		List<Integer> children;
		int minDistance = Integer.MAX_VALUE;
		
		public CentroidNode(int parent, List<Integer> children) {
			this.parent = parent;
			this.children = children;
		}
		
	}
	

	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
 
    }

}
