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

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;


public class E342 
{

	public static int mod = 1000000007;
	public static long INF = (1L << 60);
	static FastScanner2 in = new FastScanner2();
	static OutputWriter out = new OutputWriter(System.out);
 
	static int n,m;
	static Set<Integer>[] adjlist;
	static int[] subtreesize;
	static int[][] dp;
	static int LOG=19;
	static int[] level;
	static int[] parent;
	static int[] ans;
	
	public static void dfs(int v,int p,int d)
	{
		level[v]=d;
		dp[0][v]=p;
		for(int i=1;i<LOG;i++)
				dp[i][v] = dp[i-1][dp[i-1][v]];
		for(int u : adjlist[v])
		{
			if(u==p)
				continue;
			dfs(u, v, d+1);
		}
	}
	
	public static int lca(int a,int b)
	{
		if(level[a]>level[b])
			return lca(b, a);
		int d=level[b]-level[a];
		for(int i=0;i<LOG;i++)
		{
			if((d&(1<<i))>0)
				b=dp[i][b];
		}
		if(a==b)
			return a;
		for(int i=LOG-1;i>=0;i--)
		{
			if(dp[i][a]!=dp[i][b])
			{
				a=dp[i][a];
				b=dp[i][b];
			}
		}
		return dp[0][a];
	}
	
	public static int distance(int u,int v)
	{
		return level[u]+level[v]-2*level[lca(u, v)];
	}
	
	static int nn=0;
	public static void dfs1(int v,int p)
	{
		subtreesize[v]=1;
		nn++;
		for(int u : adjlist[v])
		{
			if(u==p)
				continue;
			dfs1(u, v);
			subtreesize[v]+=subtreesize[u];
		}
	}
	
	public static int dfs2(int v,int p)
	{
		for(int u : adjlist[v])
		{
			if(u==p)
				continue;
			if(subtreesize[u]>nn/2)
				return dfs2(u, v);
		}
		return v;
	}
	
	public static void decompose(int root,int p)
	{
		nn=0;
		dfs1(root, root);
		int centroid=dfs2(root, root);
		if(p==-1)
			p=centroid;
		parent[centroid]=p; //root node in centroid tree
		for(int u : adjlist[centroid])
		{
			adjlist[u].remove(centroid);
			decompose(u, centroid);
		}
		adjlist[centroid].clear();
	}
	
	public static void update(int u)
	{
		int x=u;
		while(true)
		{
			ans[x]=min(ans[x], distance(x, u));
			if(x==parent[x])
				break;
			x=parent[x];
		}
	}
	
	public static int query(int u)
	{
		int x=u;
		int ret=mod;
		while(true)
		{
			ret=min(ret, ans[x]+distance(x, u));
			if(x==parent[x])
				break;
			x=parent[x];
		}
		return ret;
	}
	
	public static void main(String[] args) 
	{

		n=in.nextInt();
		m=in.nextInt();
		adjlist=new HashSet[n+1];
		subtreesize=new int[n+1];
		parent=new int[n+1];
		dp=new int[LOG][n+1];
		level=new int[n+1];
		ans=new int[n+1];
		for(int i=1;i<=n;i++)
		{
			adjlist[i]=new HashSet<>();
		}
		for(int i=1;i<n;i++)
		{
			int u=in.nextInt();
			int v=in.nextInt();
			adjlist[u].add(v);
			adjlist[v].add(u);
		}
		dfs(1, 0, 0);
		decompose(1, -1);
		tr(parent);
		Arrays.fill(ans, mod);
		update(1);
		while(m-->0)
		{
			int t=in.nextInt();
			if(t==1)
			{
				update(in.nextInt());
			}
			else
			{
				out.println(query(in.nextInt()));
			}
		}
		out.close();

	}
	

	static class FastScanner2 
	{
		private byte[] buf = new byte[1024];
		private int curChar;
		private int snumChars;

		public int read() 
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) 
			{
				curChar = 0;
				try 
				{
					snumChars = System.in.read(buf);
				} catch (IOException e) 
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = read();
			} 
			while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = read();
			} 
			while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} 
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} 
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n)
		{
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) 
			{
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n)
		{
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) 
			{
				arr[i] = nextLong();
			}
			return arr;
		}

		private boolean isSpaceChar(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) 
		{
			return c == '\n' || c == '\r' || c == -1;
		}
	}


	static class OutputWriter 
	{
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) 
		{
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public OutputWriter(Writer writer)
		{
			this.writer = new PrintWriter(writer);
		}

		public void print(Object... objects)
		{
			for (int i = 0; i < objects.length; i++) 
			{
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void println(Object... objects)
		{
			print(objects);
			writer.println();
		}

		public void close() 
		{
			writer.close();
		}

		public void flush() 
		{
			writer.flush();
		}
	}
private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private static void debug(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	private static void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}