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
// package codeforces.pset342.e;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.LinkedBlockingDeque;

public class Main {

	static class Node {
		final int index;
		int distance;
		Set<Node> connecteds;

		Node(int index) {
			this.index = index;
			this.distance = Integer.MAX_VALUE;
			this.connecteds = new HashSet<Node>();
		}

		void connect(Node node) {
			node.connecteds.add(this);
			this.connecteds.add(node);
		}

		@Override
		public int hashCode() {
			return Integer.valueOf(index).hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Node) {
				Node other = (Node) obj;
				return this.index == other.index;
			}
			return false;
		}
	}

	// data structure of O(1) LCA calculation
	static class LcaCalculator {
		static class Footprint {
			int nodeIndex;
			int nodeDepth;

			Footprint(int nodeIndex, int nodeDepth) {
				this.nodeIndex = nodeIndex;
				this.nodeDepth = nodeDepth;
			}

			@Override
			public String toString() {
				return String.format("[%d, depth=%d]", nodeIndex, nodeDepth);
			}

		}

		final Node[] nodes;
		final ArrayList<Footprint> footprints;
		final int[] firstFindNodeIndex;
		final int[][] sparseTable;

		LcaCalculator(Node[] nodes) {
			this.nodes = nodes;
			this.footprints = new ArrayList<>(2 * nodes.length);
			this.firstFindNodeIndex = new int[nodes.length];
			this.sparseTable = init();
		}

		int[][] init() {
			// initialize RMQ_L
			eularTour();
			int n = footprints.size();
			int k = (int) log2(n);

			int[][] sparseTable = new int[n][k + 1];
			for (int i = 0; i < n; i++) {
				sparseTable[i][0] = i;
			}

			for (int j = 1; j <= k; j++) {
				int pow = (1 << (j - 1)); // 2 ^ (j-1)
				int length = n - pow;
				for (int i = 0; i < length; i++) {
					int lindex = sparseTable[i][j - 1];
					int rindex = sparseTable[i + pow][j - 1];
					int l = footprints.get(lindex).nodeDepth;
					int r = footprints.get(rindex).nodeDepth;
					sparseTable[i][j] = (l <= r) ? lindex : rindex;
				}
			}
			return sparseTable;
		}

		int calculate(int u, int v) {
			int hu = firstFindNodeIndex[u];
			int hv = firstFindNodeIndex[v];
			return this.footprints.get(rmq(hu, hv)).nodeIndex;
		}

		int distance(int u, int v) {
			int hu = firstFindNodeIndex[u];
			int hv = firstFindNodeIndex[v];
			int lca = calculate(u, v);
			int hw = firstFindNodeIndex[lca];

			// distance = Depth(u) + Depth(v) - 2*Depth(lca(u, v))
			int du = footprints.get(hu).nodeDepth;
			int dv = footprints.get(hv).nodeDepth;
			int dw = footprints.get(hw).nodeDepth;
			return (du + dv - 2 * dw);
		}

		private int rmq(int i, int j) {
			if (i > j) {
				return rmq(j, i);
			}
			int k = (int) log2(j - i + 1);
			int lindex = sparseTable[i][k];
			int rindex = sparseTable[j - (1 << k) + 1][k];
			int l = footprints.get(lindex).nodeDepth;
			int r = footprints.get(rindex).nodeDepth;
			return (l <= r) ? lindex : rindex;
		}

		double log2(int n) {
			return Math.log(n) / Math.log(2);
		}

		void eularTour() {
			// dfs start with root (node[1])
			dfs(1, 0, new boolean[nodes.length]);
		}

		void dfs(int currentIndex, int depth, boolean[] visited) {
			this.footprints.add(new Footprint(currentIndex, depth));
			firstFindNodeIndex[currentIndex] = this.footprints.size() - 1;
			visited[currentIndex] = true;
			for (Node adj : nodes[currentIndex].connecteds) {
				if (visited[adj.index]) {
					continue;
				}
				dfs(adj.index, depth + 1, visited);
				this.footprints.add(new Footprint(currentIndex, depth));
			}
		}

	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int m = s.nextInt();

		Node[] nodes = new Node[n + 1];
		for (int i = 1; i <= n; i++) {
			nodes[i] = new Node(i);
		}

		for (int i = 0; i < n - 1; i++) {
			int a = s.nextInt();
			int b = s.nextInt();
			nodes[a].connect(nodes[b]);
		}

		LcaCalculator lca = new LcaCalculator(nodes);

		HashSet<Integer> filled = new HashSet<Integer>();
		filled.add(1); // first red index

		int term = (int) Math.sqrt(m);
		for (int i = 0; i < m; i++) {
			if (i % term == 0) {
				updateAll(nodes, filled);
				filled.clear();
			}
			int t = s.nextInt();
			int v = s.nextInt();
			if (t == 1) {
				filled.add(v);
			} else {
				System.out.println(distance(v, nodes, lca, filled));
			}
		}
	}

	private static int distance(int v, Node[] nodes, LcaCalculator lca, Iterable<Integer> filled) {
		int min = nodes[v].distance;
		for (int u : filled) {
			min = Math.min(min, lca.distance(u, v));
		}
		return min;
	}

	private static void updateAll(Node[] nodes, Iterable<Integer> fillNodes) {
		LinkedBlockingDeque<Node> queue = new LinkedBlockingDeque<Node>();
		for (int index : fillNodes) {
			nodes[index].distance = 0;
			queue.add(nodes[index]);
		}
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			int nextDistance = node.distance + 1;
			for (Node adj : node.connecteds) {
				if (adj.distance > nextDistance) {
					adj.distance = nextDistance;
					queue.add(adj);
				}
			}
		}
	}

}
