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

public class main
{
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long mod = 1000000000 + 7;
	private static int[] ans;
	private static int[] pa;
	private static void soln()
	{
		int n = nextInt();
		int m = nextInt();
		
		LinkedList<Integer>[] tree = new LinkedList[n];
		for(int i = 0; i < n; i++)
			tree[i] = new LinkedList<>();
		for(int i=0;i<n-1;i++) {
			int u = nextInt() - 1;
			int v = nextInt() - 1;
			tree[u].add(0,v);
			tree[v].add(0,u);
		}
		
		LCA lca = new LCA(n, tree);
		//debug(lca.lca);
		Centroid centroid = new Centroid(n, tree);
		pa = centroid.retPar();
		//debug(pa);
		ans = new int[n];
		Arrays.fill(ans, Integer.MAX_VALUE/10);
		//debug(lca.dist(0, 4));
		update(0, lca);
		//debug(ans);
		while(m-->0) {
			int t = nextInt();
			int v = nextInt() - 1;
			if(t == 1)
				update(v, lca);
			else
				pw.println(query(v, lca));
		}
	}
	private static void update(int u,LCA lca) {
		int x = u;
		while(true) {
			ans[x] = Math.min(ans[x], lca.dist(x, u));
			if(x == pa[x])
				break;
			x = pa[x];
		}
	}
	private static int query(int u,LCA lca) {
		int x = u;
		int ret = Integer.MAX_VALUE;
		while(true) {
			ret = Math.min(ret, lca.dist(u, x) + ans[x]);
			if(x == pa[x])
				break;
			x = pa[x];
		}
		return ret;
	}
	private static class LCA{
		private int n;
		private int logn;
		private int[] lvl;
		private int[][] lca;
		public LCA(int a,LinkedList<Integer>[] tree) {
			n=a;
			logn = (int) (Math.ceil(Math.log(n)/Math.log(2)) + 1);
			lvl = new int[n];
			lca = new int[n][logn];
			
			lvl[0] = 0;
			lca[0][0] = 0;
			dfs(0, -1, tree);
			
			for(int i=1;i<logn;i++)
				for(int j=0;j<n;j++)
					lca[j][i] = lca[lca[j][i-1]][i-1];
			
		}
		private void dfs(int cur, int prev, LinkedList<Integer>[] tree) {
			Iterator<Integer> it = tree[cur].listIterator();
			while(it.hasNext()) {
				int x = it.next();
				if(x!=prev) {
					lca[x][0] = cur;
					lvl[x] = lvl[cur] + 1;
					dfs(x, cur, tree);
				}
			}
		}
		public int lca(int a,int b) {
			if(lvl[a] > lvl[b]) {
				int tmp = a;
				a = b;
				b = tmp;
			}
			int d = lvl[b] - lvl[a];
			for(int i=0;i<logn;i++) {
				if((d&(1<<i))!=0)
					b = lca[b][i];
			}
			if(a == b)
				return a;
			for(int i = logn - 1; i >= 0; i--) {
				if(lca[a][i] != lca[b][i]) {
					a = lca[a][i];
					b = lca[b][i];
				}
			}
			return lca[a][0];
		}
		public int dist(int a,int b) {
			return lvl[a] + lvl[b] - 2*lvl[lca(a,b)];
		}
	}
	
	private static class Centroid{
		private int n;
		private LinkedList<Integer>[] tree;
		private int[] sPar;
		private int[] size;
		private int nn;
		
		public Centroid(int a,LinkedList<Integer>[] l) {
			n=a;
			tree=l;
			size = new int[n];
			sPar = new int[n];
			
			decompose(0, -1);
		}
		
		private void decompose(int cur,int prev) {
			nn = 0;
			dfs(cur,cur);
			
			Integer centroid = findCentroid(cur, cur);
			//System.out.println(centroid);
			if(prev == -1)
				prev = centroid;
			
			sPar[centroid] = prev;
			Iterator<Integer> it = tree[centroid].listIterator();
			while(it.hasNext()) {
				int x = it.next();
				tree[x].remove(centroid);
				decompose(x, centroid);
			}
			tree[centroid].clear();
		}
		
		private void dfs(int cur, int prev) {
			size[cur] = 1;
			nn++;
			Iterator<Integer> it = tree[cur].listIterator();
			while(it.hasNext()) {
				int x = it.next();
				if(x!=prev) {
					dfs(x, cur);
					size[cur]+=size[x];
				}
			}
		}
		
		private int findCentroid(int cur,int prev) {
			Iterator<Integer> it = tree[cur].listIterator();
			while(it.hasNext()) {
				int x = it.next();
				if(x!=prev && size[x] > nn/2){
					return findCentroid(x,cur);
				}
			}
			return cur;
		}
		private int[] retPar() {
			return sPar;
		}
	}
	private static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
	
	private static class Pair implements Comparable<Pair>{
		long val;
		int br;
		public Pair(long a,int b) {
			val=a;
			br=b;
		}
		@Override
		public int compareTo(Pair arg0)
		{
			return (int) (this.val-arg0.val);
		}
	}
	private static long pow(long a, long b, long c)
	{
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}

	private static long gcd(long n, long l)
	{
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}
	public static void main(String[] args) throws Exception
	{
//		new Thread(null, new Runnable()
//		{
//			@Override
//			public void run()
//			{
//				/*
//				 * try { InputReader(new
//				 * FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); } catch
//				 *) (FileNotFoundException e) { // TODO Auto-generated catch block
//				 * e.printStackTrace(); }
//				 */
//				InputReader(System.in);
//				pw = new PrintWriter(System.out);
//				/*
//				 * try { pw=new PrintWriter(new
//				 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
//				 * (FileNotFoundException e) { // TODO Auto-generated catch block
//				 * e.printStackTrace(); }
//				 */
//				soln();
//				pw.close();
//			}
//		}, "1", 1 << 26).start();

		/*
		 * try { InputReader(new
		 * FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); } catch
		 * (FileNotFoundException e) { // TODO Auto-generated catch block
		 * e.printStackTrace(); }
		 */
		 InputReader(System.in);
		 pw = new PrintWriter(System.out);
		/*
		 * try { pw=new PrintWriter(new
		 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
		 * (FileNotFoundException e) { // TODO Auto-generated catch block
		 * e.printStackTrace(); }
		 */
		soln();
		pw.close();
	}

	public static void InputReader(InputStream stream1)
	{
		stream = stream1;
	}

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

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

	private static int read()
	{
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars)
		{
			curChar = 0;
			try
			{
				numChars = stream.read(buf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static 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;
	}

	private static 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;
	}

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

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

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

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

	private static void pArray(int[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c)
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private static char nextChar()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(c))
			c = read();
		return c1;
	}

	private interface SpaceCharFilter
	{
		public boolean isSpaceChar(int ch);
	}
}