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.*;
import java.util.*;
import java.math.*;

public class E implements Runnable {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	final int inf = Integer.MAX_VALUE / 2;

	class SparseTable {
		private int[][] keysTable;
		private int[] values;
		private int[] pows;

		public SparseTable(int[] keys, int[] values) {
			this.values = values;

			int n = keys.length;
			buildPows(n);
			buildTable(n, keys);
		}

		private void buildTable(int n, int[] keys) {
			keysTable = new int[pows[n] + 1][0];
			keysTable[0] = new int[n];
			System.arraycopy(keys, 0, keysTable[0], 0, n);
			for (int pow = 1; pow <= pows[n]; pow++) {
				int howMuch = n - (1 << pow) + 1;
				int half = (1 << (pow - 1));
				keysTable[pow] = new int[howMuch];
				for (int l = 0; l < howMuch; l++) {
					int firstKey = keysTable[pow - 1][l];
					int secondKey = keysTable[pow - 1][l + half];
					keysTable[pow][l] = (values[firstKey] < values[secondKey] ? firstKey
							: secondKey);
				}
			}
		}

		private void buildPows(int n) {
			pows = new int[n + 1];
			int pow = 0;
			for (int i = 1; i <= n; i++) {
				while ((1 << (pow + 1)) <= i)
					++pow;
				pows[i] = pow;
			}
		}

		public int get(int l, int r) {
			if (l > r) {
				int t = l;
				l = r;
				r = t;
			}
			int distance = r - l + 1;
			int pow = pows[distance];
			int powValue = (1 << pow);
			//out.println("pow: " + pow + " " + l + " " + distance + " " + powValue);

			int leftKey = keysTable[pow][l];
			int rightKey = keysTable[pow][l + distance - powValue];

			return values[leftKey] < values[rightKey] ? leftKey : rightKey;
		}
	}

	private void solve() throws IOException {
		int vertexesCount = nextInt(), queriesCount = nextInt();
		int edgesCount = vertexesCount - 1;
		int[] edgesTo = new int[edgesCount * 2], edgesNext = new int[edgesCount * 2], edgesFirst = new int[vertexesCount];
		Arrays.fill(edgesFirst, -1);
		for (int i = 0; i < edgesCount; i++) {
			int u = nextInt() - 1, v = nextInt() - 1;
			addEdge(edgesTo, edgesNext, edgesFirst, 2 * i, u, v);
			addEdge(edgesTo, edgesNext, edgesFirst, 2 * i + 1, v, u);
		}
		
		int[] firstTimes = new int[vertexesCount], heights = new int[vertexesCount];

		SparseTable st = buildLCA(vertexesCount, edgesTo, edgesNext,
				edgesFirst, firstTimes, heights);
		
		int segmentSize = 800;
		int[] vertexesToColor = new int[segmentSize];
		int vertexesToColorCount = 0;
		boolean[] color = new boolean[vertexesCount];
		int[] nearestColored = new int[vertexesCount];
		Arrays.fill(nearestColored, inf);

		vertexesToColor[vertexesToColorCount++] = 0;

		for (int queryId = 0; queryId < queriesCount; queryId++) {
			int type = nextInt(), vertex = nextInt() - 1;

			if (type == 1) {
				vertexesToColor[vertexesToColorCount++] = vertex;
				if (vertexesToColorCount == segmentSize) {
					for (int i = 0; i < vertexesToColorCount; i++)
						color[vertexesToColor[i]] = true;
					vertexesToColorCount = 0;
					updateNearestColored(vertexesCount, edgesTo, edgesNext,
							edgesFirst, color, nearestColored);
				}
			} else if (type == 2) {
				int result = nearestColored[vertex];
				for (int i = 0; i < vertexesToColorCount; i++)
					result = Math.min(
							result,
							getDistance(firstTimes, heights, st, vertex,
									vertexesToColor[i]));
				out.println(result);
			} else {
				throw new AssertionError();
			}
		}
	}

	private SparseTable buildLCA(int vertexesCount, int[] edgesTo,
			int[] edgesNext, int[] edgesFirst, int[] firstTimes, int[] heights) {
		List<Integer> history = new ArrayList<Integer>();
		lcaDFS(0, -1, edgesTo, edgesNext, edgesFirst, history, 0, heights);
		int[] historyArr = toArray(history);
		Arrays.fill(firstTimes, inf);
		for (int i = 0; i < history.size(); i++) {
			int u = historyArr[i];
			firstTimes[u] = Math.min(firstTimes[u], i);
		}
		SparseTable st = new SparseTable(historyArr, heights);
		return st;
	}

	private int[] toArray(List<Integer> list) {
		int[] result = new int[list.size()];
		for (int i = 0; i < list.size(); i++)
			result[i] = list.get(i);
		return result;
	}

	private void lcaDFS(int u, int parent, int[] edgesTo, int[] edgesNext,
			int[] edgesFirst, List<Integer> history, int height, int[] heights) {
		history.add(u);
		heights[u] = height;

		for (int ptr = edgesFirst[u]; ptr != -1; ptr = edgesNext[ptr]) {
			int v = edgesTo[ptr];
			if (v != parent) {
				lcaDFS(v, u, edgesTo, edgesNext, edgesFirst, history,
						height + 1, heights);
				history.add(u);
			}
		}

	}

	private int getDistance(int[] firstTimes, int[] heights, SparseTable st,
			int u, int v) {
		if (u == v)
			return 0;

		int lca = st.get(firstTimes[u], firstTimes[v]);
		return Math.abs(heights[u] - heights[lca])
				+ Math.abs(heights[v] - heights[lca]);
	}

	private void updateNearestColored(int vertexesCount, int[] edgesTo,
			int[] edgesNext, int[] edgesFirst, boolean[] color,
			int[] nearestColored) {
		firstDFS(0, -1, edgesTo, edgesNext, edgesFirst, color, nearestColored);
		secondDFS(0, -1, edgesTo, edgesNext, edgesFirst, color, nearestColored,
				vertexesCount);
	}

	private void secondDFS(int u, int parent, int[] edgesTo, int[] edgesNext,
			int[] edgesFirst, boolean[] color, int[] nearestColored,
			int topDistance) {
		// out.println("Second dfs: " + u + " " + topDistance);
		nearestColored[u] = Math.min(nearestColored[u], topDistance);

		int minVertex = -1, minResult = inf;
		int secondMinVertex = -1, secondMinResult = inf;

		if (nearestColored[u] == 0) {
			minResult = secondMinResult = 0;
			minVertex = secondMinVertex = u;
		} else {
			for (int ptr = edgesFirst[u]; ptr != -1; ptr = edgesNext[ptr]) {
				int v = edgesTo[ptr], distance = nearestColored[v] + 1;

				if (distance < minResult) {
					secondMinVertex = minVertex;
					secondMinResult = minResult;
					minVertex = v;
					minResult = distance;
				} else if (distance < secondMinResult) {
					secondMinVertex = v;
					secondMinResult = distance;
				}
			}
		}

		for (int ptr = edgesFirst[u]; ptr != -1; ptr = edgesNext[ptr]) {
			int v = edgesTo[ptr];
			// out.println("Go: " + u + " " + v);

			if (v != parent) {
				int newDistance = (v != minVertex) ? minResult
						: secondMinResult;
				newDistance = Math.min(newDistance, topDistance);

				secondDFS(v, u, edgesTo, edgesNext, edgesFirst, color,
						nearestColored, newDistance + 1);
			}
		}
	}

	private void firstDFS(int u, int parent, int[] edgesTo, int[] edgesNext,
			int[] edgesFirst, boolean[] color, int[] nearestColored) {
		if (color[u])
			nearestColored[u] = 0;

		for (int ptr = edgesFirst[u]; ptr != -1; ptr = edgesNext[ptr]) {
			int v = edgesTo[ptr];

			if (v != parent) {
				firstDFS(v, u, edgesTo, edgesNext, edgesFirst, color,
						nearestColored);
				nearestColored[u] = Math.min(nearestColored[u],
						nearestColored[v] + 1);
			}
		}
	}

	private void addEdge(int[] edgesTo, int[] edgesNext, int[] edgesFirst,
			int id, int u, int v) {
		edgesTo[id] = v;
		edgesNext[id] = edgesFirst[u];
		edgesFirst[u] = id;
	}

	public static void main(String[] args) {
		new E().run();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}