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
/*
 * Code Author: Akshay Miterani
 * DA-IICT
 */
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class C1 {

	InputReader in;
	PrintWriter out;
	C1() throws IOException {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String args[]) {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new C1();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	//--------------------My Code Starts Here----------------------
	static long mod=(long)1e9+7;
	public void solve() {
		int n=in.nextInt();
		int m=in.nextInt();
		int sqrt=(int)Math.sqrt(m);
		ArrayList<TreeSet<Integer>> arr=new ArrayList<>();
		for(int i=0;i<n;i++){
			arr.add(new TreeSet<Integer>());
		}
		for(int i=1;i<n;i++){
			int u=in.nextInt()-1;
			int v=in.nextInt()-1;
			arr.get(u).add(v);
			arr.get(v).add(u);
		}
		LcaSparseTable lst=new LcaSparseTable(arr, 0);
		centroidDecomposition cd=new centroidDecomposition(n, 0, arr, lst);
		cd.update(0);
		while(m-->0){
			int type=in.nextInt();
			int node=in.nextInt()-1;
			if(type==1){
				cd.update(node);
			}
			else{
				out.println(cd.query(node));
			}
		}
	}
	//---------------------My Code Ends Here------------------------
	class centroidDecomposition{
		int depth[], parent[];
		int inf=(int)(1e9);
		int center=-1,n;
		ArrayList<TreeSet<Integer>> tree;
		long ans[];
		LcaSparseTable lst;
		public centroidDecomposition(int nn, int root, ArrayList<TreeSet<Integer>> tr, LcaSparseTable lt) {
			n=nn;
			depth = new int[n];
			parent = new int[n];
			ans = new long[n];
			Arrays.fill(depth, -1);
			Arrays.fill(ans, inf);
			tree=tr;
			lst=lt;
			findCentroid(root, n, -1, 0);
		}
		void findCentroid(int root, int size, int last, int h) {

	        center = -1;
	        dfs(root, -1, size);
	        depth[center] = h;
	        parent[center] = last;
	        int cn = center;

	        for (int u : tree.get(center))
	            if (depth[u] == -1)
	                findCentroid(u, size/2, cn, h+1);
	    }

	    int dfs(int v, int p, int n) {

	        int cnt = 1;
	        for (int u : tree.get(v))
	            if (u != p && depth[u] == -1)
	                cnt += dfs(u, v, n);

	        if (center == -1 && (cnt*2 >= n || p == -1))
	            center = v;

	        return cnt;
	    }
	    
	    void update(int v){
	    	int u = v;
	    	while(u!=-1){
	    		ans[u] = Math.min(ans[u], lst.dist(u, v));
	            u = parent[u];
	    	}
	    }
	    
	    long query(int v){
	    	long res = ans[v];
	        int u = v;
	        while (u != -1) {
	            res = Math.min(res, ans[u]+lst.dist(u, v));
	            u = parent[u];
	        }
	        return res;
	    }
	}
	class LcaSparseTable {

		int len;
		int[][] up;
		int[] tin;
		int[] tout;
		int time;
		long d[];
		void dfs(ArrayList<TreeSet<Integer>> tree, int u, int p) {
			tin[u] = time++;
			up[0][u] = p;
			for (int i = 1; i < len; i++)
				up[i][u] = up[i - 1][up[i - 1][u]];
			for (int v : tree.get(u))
				if (v != p)
					dfs(tree, v, u);
			tout[u] = time++;
		}

		public LcaSparseTable(ArrayList<TreeSet<Integer>> tree, int root) {
			int n = tree.size();
			len = 1;
			while ((1 << len) <= n) ++len;
			up = new int[len][n];
			tin = new int[n];
			tout = new int[n];
			dfs(tree, root, root);
			d=new long[n];
			dfs2(root, root, 0, tree);
		}

		boolean isParent(int parent, int child) {
			return tin[parent] <= tin[child] && tout[child] <= tout[parent];
		}

		public int lca(int a, int b) {
			if (isParent(a, b))
				return a;
			if (isParent(b, a))
				return b;
			for (int i = len - 1; i >= 0; i--)
				if (!isParent(up[i][a], b))
					a = up[i][a];
			return up[0][a];
		}
		
		void dfs2(int x, int p, int dist, ArrayList<TreeSet<Integer>> arr){
			d[x]=dist;
			for(int nei:arr.get(x)){
				if(nei!=p){
					dfs2(nei, x, dist+1, arr);
				}
			}
		}
		
		long dist(int x,int y){
			return d[x]+d[y]-2*d[lca(x, y)];
		}
	}
	static long modulo(long a,long b,long c) {
		long x=1;
		long y=a;
		while(b > 0){
			if(b%2 == 1){
				x=(x*y)%c;
			}
			y = (y*y)%c; // squaring the base
			b /= 2;
		}
		return  x%c;
	}
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		Pair(int xx,int yy){
			x=xx;
			y=yy;
		}
		@Override
		public int compareTo(Pair o) {
			if(Long.compare(this.x, o.x)!=0)
				return Long.compare(this.x, o.x);
			else
				return Long.compare(this.y, o.y);
		}
	}
	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}     