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.awt.Label;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.xml.bind.ValidationEvent;

import org.omg.PortableServer.ID_ASSIGNMENT_POLICY_ID;

public class Solutions {

	static Scanner in = new Scanner();
	static PrintWriter out = new PrintWriter(System.out);
	static HashSet<Integer> tree[];
	static int number_node_now, n, m, logn = 17;
	static int size[], lebal[];

	public static void main(String[] test) throws NumberFormatException, IOException {
		n = in.nextInt();
		m = n - 1;
		int q = in.nextInt();
		tree = new HashSet[n];
		for (int i = 0; i < n; i++) {
			tree[i] = new HashSet<>();
		}
		for (int i = 0; i < m; i++) {
			int u = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			tree[u].add(v);
			tree[v].add(u);
		}
		preprocess();

		size = new int[n];
		lebal = new int[n];

		decompostion(0, -1);

		ans = new int[n];
		Arrays.fill(ans, (int) 1e9);
		update(0);
		for (int i = 0; i < q; i++) {
			int type = in.nextInt();
			int u = in.nextInt() - 1;
			if (type == 1) {
				update(u);
			} else {
				out.println(query(u));
			}
		}

		out.flush();
		out.close();
	}

	static void update(int u) {
		int x = u;
		ans[u] = 0;
		while (x != lebal[x]) {
			x = lebal[x];
			ans[x] = Math.min(ans[x], dist(x, u));
		}
	}

	static int query(int u) {
		int x = u;
		int ret = ans[u];
		while (x != lebal[x]) {
			x = lebal[x];
			ret = Math.min(ret, ans[x] + dist(x, u));
		}
		return ret;
	}

	static int dp[][], level[];
	static int ans[];

	static void dfs0(int s, int p) {
		for (int x : tree[s]) {
			if (x != p) {
				dp[0][x] = s;
				level[x] = level[s] + 1;
				dfs0(x, s);
			}
		}
	}

	static void preprocess() {
		level = new int[n];
		dp = new int[logn][n];

		dfs0(0, -1);
		for (int i = 1; i < logn; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = dp[i - 1][dp[i - 1][j]];
			}
		}
	}

	static int lca(int u, int v) {
		if (level[u] > level[v]) {
			u ^= v;
			v ^= u;
			u ^= v;
		}
		int dist = level[v] - level[u];
		for (int i = 0; i < logn; i++) {
			if ((dist & (1 << i)) > 0)
				v = dp[i][v];
		}
		if (u == v)
			return u;
		for (int i = logn - 1; i >= 0; i--) {
			if (dp[i][u] != dp[i][v]) {
				u = dp[i][u];
				v = dp[i][v];
			}
		}
		return dp[0][u];
	}

	static int dist(int u, int v) {
		return level[u] + level[v] - 2 * level[lca(u, v)];
	}

	static void decompostion(int node, int parent) {
		number_node_now = 0;
		dfs(node, node);
		int centroid_node = centroid(node, node);
		if (parent == -1) {
			parent = centroid_node;
		}
		lebal[centroid_node] = parent;
		for (Integer u : tree[centroid_node]) {
			tree[u].remove((centroid_node));
			decompostion(u, centroid_node);
		}
		tree[centroid_node].clear();
	}

	static int centroid(int node, int par) {
		for (Integer u : tree[node]) {
			if (u != par && size[u] > number_node_now / 2) {
				return centroid(u, node);
			}
		}
		return node;
	}

	static void dfs(int node, int par) {
		number_node_now++;
		size[node] = 1;
		for (Integer u : tree[node]) {
			if (u != par) {
				dfs(u, node);
				size[node] += size[u];
				;
			}
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public Scanner(FileReader fileReader) throws FileNotFoundException {
			br = new BufferedReader(fileReader);
		}

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}