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.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.util.ArrayDeque;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.Collection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
	public void solve(int testNumber, FastScanner in, PrintWriter out) {
		n = in.nextInt();
		int numQueries = in.nextInt();
		initTree(n);
		for (int i = 0; i < n - 1; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			addEdge(a, b);
			addEdge(b, a);
		}
		precalcLCA();
		buildCentroidDecomposition();
		int[] best = depth.clone();
		for (int queryId = 0; queryId < numQueries; queryId++) {
			int type = in.nextInt();
			int v = in.nextInt() - 1;
			int ans = Integer.MAX_VALUE;
			for (int u = v; u >= 0; u = centroidDecompositionParent[u]) {
				if (type == 1) {
					best[u] = Math.min(best[u], distance(u, v));
				} else {
					ans = Math.min(ans, best[u] + distance(u, v));
				}
			}
			if (type == 2) {
				out.println(ans);
			}
		}
	}

	int n;
	int[] firstEdge;
	int[] nextEdge;
	int[] edgeDst;
	int numEdges;

	private void initTree(int n) {
		this.n = n;
		firstEdge = new int[n];
		Arrays.fill(firstEdge, -1);
		numEdges = 0;
		nextEdge = new int[2*n];
		edgeDst = new int[2*n];
	}

	private void addEdge(int a, int b) {
		int e = numEdges++;
		nextEdge[e] = firstEdge[a];
		firstEdge[a] = e;
		edgeDst[e] = b;
	}

	boolean[] usedInDecomposition;
	int[] subtreeSize;
	int[] generation;
	int lastGeneration;
	int[] parent;
	int[] centroidDecompositionParent;
	private int buildCentroidDecomposition() {
		usedInDecomposition = new boolean[n];
		subtreeSize = new int[n];
		parent = new int[n];
		generation = new int[n];
		lastGeneration = 0;
		centroidDecompositionParent = new int[n];
		int root = decompose(0);
		centroidDecompositionParent[root] = -1;
		return root;
	}

	private int decompose(int s) {
		List<Integer> comp = new ArrayList<>();
		parent[s] = -1;
		++lastGeneration;
		generation[s] = lastGeneration;
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(s);
		while (!q.isEmpty()) {
			int v = q.poll();
			comp.add(v);
			subtreeSize[v] = 1;
			for (int e = firstEdge[v]; e >= 0; e = nextEdge[e]) {
				int u = edgeDst[e];
				if (usedInDecomposition[u]) {
					continue;
				}
				if (u == parent[v]) {
					continue;
				}
				if (generation[u] != lastGeneration) {
					parent[u] = v;
					q.offer(u);
				}
			}
		}
		for (int i = comp.size() - 1; i > 0; i--) {
			int v = comp.get(i);
			subtreeSize[parent[v]] += subtreeSize[v];
		}
		int c = -1;
		for (int v : comp) {
			boolean good = true;
			for (int e = firstEdge[v]; e >= 0; e = nextEdge[e]) {
				int u = edgeDst[e];
				if (u == parent[v]) {
					continue;
				}
				if (usedInDecomposition[u]) {
					continue;
				}
				if (2*subtreeSize[u] > comp.size()) {
					good = false;
				}
			}
			if (2*(comp.size() - subtreeSize[v]) > comp.size()) {
				good = false;
			}
			if (good) {
				c = v;
				break;
			}
		}
		if (c < 0) {
			throw new AssertionError();
		}
		usedInDecomposition[c] = true;
		// c is a centroid of the subtree containing vertex s
		for (int e = firstEdge[c]; e >= 0; e = nextEdge[e]) {
			int u = edgeDst[e];
			if (usedInDecomposition[u]) {
				continue;
			}
			centroidDecompositionParent[decompose(u)] = c;
		}
		return c;
	}


	int[][] ancestor;
	int[] depth;
	int[] timeIn;
	int[] timeOut;
	int globalTime;
	private void precalcLCA() {
		int log = 1;
		while ((1 << log) <= n) {
			++log;
		}
		ancestor = new int[log][n];
		for (int[] arr : ancestor) {
			Arrays.fill(arr, -1);
		}
		depth = new int[n];
		timeIn = new int[n];
		timeOut = new int[n];
		dfsLCA(0);
		for (int k = 0; k + 1 < log; k++) {
			for (int i = 0; i < n; i++) {
				int p = ancestor[k][i];
				if (p >= 0) {
					ancestor[k + 1][i] = ancestor[k][p];
				}
			}
		}
	}

	private void dfsLCA(int v) {
		timeIn[v] = globalTime++;
		for (int e = firstEdge[v]; e >= 0; e = nextEdge[e]) {
			int u = edgeDst[e];
			if (u != ancestor[0][v]) {
				ancestor[0][u] = v;
				depth[u] = depth[v] + 1;
				dfsLCA(u);
			}
		}
		timeOut[v] = globalTime++;
	}

	private boolean isAncestor(int parent, int son) {
		return timeIn[parent] <= timeIn[son] && timeOut[son] <= timeOut[parent];
	}

	private int lca(int a, int b) {
		if (isAncestor(a, b)) return a;
		if (isAncestor(b, a)) return b;
		for (int k = ancestor.length - 1; k >= 0; k--) {
			int p = ancestor[k][a];
			if (p >= 0 && !isAncestor(p, b)) {
				a = p;
			}
		}
		return ancestor[0][a];
	}

	private int distance(int a, int b) {
		int c = lca(a, b);
		return depth[a] + depth[b] - 2*depth[c];
	}

}

class FastScanner {

	private BufferedReader in;
	private StringTokenizer st;

	public FastScanner(InputStream stream) {
		in = new BufferedReader(new InputStreamReader(stream));
	}

	public String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

}

