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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class B {

	/*
	 * Centroid Decomposition
	 */
	static ArrayList<Integer>[] adjList;
	static int[] P, subSize, label, dist[];

	static int findSize(int u, int p)
	{
		int sz = 1;
		for(int i = 0; i < adjList[u].size(); ++i)
		{
			int v = adjList[u].get(i);
			if(v != p && P[v] == -2)
				sz += findSize(v, u);
		}
		return subSize[u] = sz;
	}

	static int decompose(int u, int p, int n, int lb)
	{
		if(p == -1)
			n = findSize(u, -1);
		int idx = -1;
		for(int i = 0; i < adjList[u].size(); ++i)
		{
			int v = adjList[u].get(i);
			if(v != p && P[v] == -2 && subSize[v] > n / 2)
			{
				idx = v;
				break;
			}
		}
		if(idx != -1)
			return decompose(idx, u, n, lb);

		//u is centroid, decompose forest
		P[u] = -1;
		for(int v: adjList[u])
			if(P[v] == -2)
				P[decompose(v, -1, n, lb + 1)] = u;
		label[u] = lb;
		return u;
	}
	
	/*
	 * Distance Preprocessing
	 */
	static void computeDist(int s, int lb, int u, int p, int d)
	{
		dist[lb][u] = d;
		for(int i = 0; i < adjList[u].size(); ++i)
		{
			int v = adjList[u].get(i);
			if(v != p && label[v] >= lb)
				computeDist(s, lb, v, u, d + 1);
		}
	}
	
	/*
	 * Update and Query
	 */
	static int[] near;
	
	static void update(int v)
	{
		int u = v, lb = label[v];
		while(u != -1)
		{
			near[u] = Math.min(near[u], dist[lb][v]);
			u = P[u];
			--lb;
		}
	}
	
	static int query(int v)
	{
		int ans = (int)1e9, u = v, lb = label[v];
		while(u != -1)
		{
			ans = Math.min(ans, near[u] + dist[lb][v]);
			u = P[u];
			--lb;
		}
		return ans;
	}
	
	public static void main(String[] args) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt(), m = sc.nextInt();
		adjList = new ArrayList[n];
		for(int i = 0; i < n; ++i)
			adjList[i] = new ArrayList<Integer>();
		for(int i = 1; i < n; ++i)
		{
			int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
			adjList[u].add(v);
			adjList[v].add(u);
		}
		
		// construct centroid tree in P
		P = new int[n];
		subSize = new int[n];
		label = new int[n];
		Arrays.fill(P, -2);
		decompose(0, -1, n, 0);

		// preprocess needed distances
		dist = new int[18][n];
		for(int i = 0; i < n; ++i)
			computeDist(i, label[i], i, -1, 0);
		
		// process queries
		near = new int[n];
		Arrays.fill(near, n);
		StringBuilder sb = new StringBuilder();
		update(0);
		while(m-->0)
			if(sc.nextInt() == 1)
				update(sc.nextInt() - 1);
			else
				sb.append(query(sc.nextInt() - 1)+"\n");
		
		out.print(sb);
		out.flush();
		out.close();
	}
	

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(FileReader r){	br = new BufferedReader(r);}

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

		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 double nextDouble() throws IOException { return Double.parseDouble(next()); }

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


	}
}

