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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class B {

	static ArrayList<Integer>[] adjList;
	static int[] P, subSize;

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

	static int decompose(int u, int p, int n)
	{
		if(p == -1)
			n = findSize(u, -1);
		int idx = -1;
		for(int v: adjList[u])
			if(v != p && P[v] == -2 && subSize[v] > n / 2)
			{
				idx = v;
				break;
			}
		if(idx != -1)
			return decompose(idx, u, n);

		//u is centroid, decompose forest
		P[u] = -1;
		for(int v: adjList[u])
			if(P[v] == -2)
				P[decompose(v, -1, n)] = u;
		return u;
	}
	
	static int[] near;
	
	static void update(int v)
	{
		int u = v;
		while(u != -1)
		{
			near[u] = Math.min(near[u], lca.dist(u, v));
			u = P[u];
		}
	}
	
	static int query(int v)
	{
		int ans = (int)1e9, u = v;
		while(u != -1)
		{
			ans = Math.min(ans, near[u] + lca.dist(u, v));
			u = P[u];
		}
		return ans;
	}
	
	static LCA lca;
	
	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);
		}
		
		// LCA preprocessing
		lca = new LCA(adjList, n);
		
		// construct centroid tree in P
		P = new int[n];
		subSize = new int[n];
		Arrays.fill(P, -2);
		decompose(0, -1, n);
		
		// 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 LCA
	{
		int k, L[], P[][];
		
		LCA(ArrayList<Integer>[] adjList, int n)
		{
			L = new int[n];
			Arrays.fill(L, -1);
			
			k = 0; while(1<<k+1 < n) ++k;
			P = new int[k + 1][n];
			for(int i = 0; i <= k; ++i)
				Arrays.fill(P[i], -1);
			L[0] = 0;
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(0);
			while(!q.isEmpty())
			{
				int u = q.remove();
				for(int v: adjList[u])
					if(L[v] == -1)
					{
						L[v] = L[u] + 1;
						P[0][v] = u;
						q.add(v);
					}
			}
			
			for(int j = 1; j <= k; ++j)
				for(int i = 0; i < n; ++i)
					if(P[j - 1][i] != -1)
						P[j][i] = P[j - 1][P[j - 1][i]];
		}
		
		int query(int p, int q)
		{
			if(L[p] < L[q]) { q ^= p; p ^= q; q ^= p; }
			
			int log = k;
			
			while(log >= 0) { if(L[p] - (1<<log) >= L[q]) p = P[log][p]; --log; }
			
			if(p == q)
				return p;
			for(int i = k; i >= 0; --i)
				if(P[i][p] != -1 && P[i][p] != P[i][q])
				{
					p = P[i][p];
					q = P[i][q];
				}
			return P[0][p];
		}
		
		int dist(int u, int v)
		{
			int w = query(u, v), ret = L[u] + L[v] - 2 * L[w];

			return ret;
		}
		
	}

	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();}


	}
}

