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

public class xeniaandtree {
	static int N=(int)(1e5+10);
	static int logn=20;
	static int inf=(int)(1e9);
	static TreeSet<Integer> g[];
	static int par[]=new int[N];
	static int sub[]=new int[N];
	static int level[]=new int[N];
	static int ans[]=new int[N];
	static int dp[][]=new int[logn][N];
	static int n,m;
	
	public static void main(String[] aegs)
	{
		InputReader in=new InputReader(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		n=in.nextInt();
		m=in.nextInt();
		g=new TreeSet[n];
		for(int i=0;i<n;i++)
		{
			g[i]=new TreeSet<Integer>();
		}
		for(int i=0;i<n-1;i++)
		{
			int u=in.nextInt()-1;
			int v=in.nextInt()-1;
			g[u].add(v);
			g[v].add(u);
		}
		preprocess();
		decompose(0,-1);
		for(int i=0;i<n;i++)
			ans[i]=inf;
		update(0);//first node is initially painted red
		while(m-->0)
		{
			int t=in.nextInt();
			int v=in.nextInt()-1;
		
			if(t==1)
				update(v);
			else
			{
				pw.println((query(v)));
			}
		}
		pw.close();
		
	}
	static void preprocess()
	{
		level[0]=0;
		dp[0][0]=0;
		dfs0(0);
		for(int i=1;i<logn;i++)
		{
			for(int j=0;j<n;j++)
			{
				dp[i][j]=dp[i-1][dp[i-1][j]];
			}
		}
	}
	static void dfs0(int u)
	{
		for(int v:g[u])
		{
			
			if(v!=dp[0][u])
			{
				dp[0][v]=u;
				level[v]=level[u]+1;
				dfs0(v);
			}
		}
	}
	static int lca(int a,int b)
	{
		if(level[a]>level[b])
		{
			int temp=b;
			b=a;
			a=temp;
		}
		int d=level[b]-level[a];
		for(int i=0;i<logn;i++)
		{
			if((d&(1<<i))>0)
			{
				b=dp[i][b];
			}
		}
		if(a==b)
		{
			return a;
		}
		for(int i=logn-1;i>=0;i--)
		{
			if(dp[i][a]!=dp[i][b])
			{
				a=dp[i][a];
				b=dp[i][b];
			}
		}
		return dp[0][a];
	}
	
	static int dist(int u,int v)
	{
		return level[u]+level[v]-2*level[lca(u,v)];
	}
	static int nn=0;
	static void dfs1(int u,int p)
	{
		sub[u]=1;
		nn++;
		for( int it:g[u])
			if(it!=p)
			{
				dfs1(it,u);
				sub[u]+=sub[it];
			}
	}
	static int dfs2(int u,int p)
	{
		for(int it:g[u])
			if(it!=p && sub[it]>nn/2)
				return dfs2(it,u);
		return u;
	}
	static void decompose(int root,int p)
	{
		nn=0;
		dfs1(root,root);
		int centroid = dfs2(root,root);
		if(p==-1)p=centroid;
		par[centroid]=p;
		for(int it:g[centroid])
		{
			g[it].remove(centroid);
			decompose(it,centroid);
		}
		g[centroid].clear();
	}
	static void update(int u)
	{
		int x = u;
		while(true)
		{
			ans[x] =Math. min(ans[x],dist(x,u));
			if(x==par[x])
				break;
			x = par[x];
		}
	}
	static int query(int u)
	{
		int x = u;
		int ret=inf;
		while(true)
		{
			ret = Math.min(ret,dist(u,x) + ans[x]);
			if(x==par[x])
				break;
			x = par[x];
		}
		return ret;
	}
	static class InputReader {
		 
		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar;
		private int snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
 
			int res = 0;
 
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
 
			return res * sgn;
		}
 
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
 
			long res = 0;
 
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
 
			return res * sgn;
		}
 
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

}
