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

public class E {

	final static int N=100000+10;
    final static int LOGN=20;
    static ArrayList<Integer> adj[]=(ArrayList<Integer>[])new ArrayList[N];
    static int sub[]=new int[N];
    static int nn;
    static int U[]=new int[N];
    static int V[]=new int[N];
    static boolean deleted[]=new boolean[N];
    static int par[]=new int[N];
    static int level[]=new int[N];
    static int dist[][]=new int[LOGN][N];
    static int ans[]=new int[N];
    final static int oo=987654321;

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		adj=new ArrayList[N];
		Arrays.fill(ans, oo);
		for(int i=0;i<N;i++)
			adj[i]=new ArrayList<>();
		for(int i=1;i<n;i++) {
            U[i]=sc.nextInt();
            V[i]=sc.nextInt();
            adj[U[i]].add(i);
            adj[V[i]].add(i);
        }
        decompose(1, -1);
		color_red(1);
		while(m-->0) {
			int t=sc.nextInt();
			if(t==1)
				color_red(sc.nextInt());
			else
				System.out.println(compute_distance(sc.nextInt()));
		}
	}

	static int compute_distance(int u) {
		int lvl=level[u];
		int x=u;
		int min=ans[u]+dist[lvl][u];
		while(x!=par[x]) {
			x=par[x];
			lvl=level[x];
			min=Math.min(min,ans[x]+dist[lvl][u]);
		}
		return min;
	}

	static void color_red(int i) {
		ans[i]=0;
		int lvl=level[i];
		int x=i;
		while(x!=par[x]) {
			x=par[x];
			lvl=level[x];
			ans[x]=Math.min(ans[x],dist[lvl][i]);
		}
		// for(int xx:ans)
		// 	System.out.print(xx+" ");
	}

	static void decompose(int root, int p) {
        nn=0; 
        dfs1(root, root); 
        int centroid = find_centroid(root, root);
        if(p==-1) p=centroid;
        add_edge_centroid_tree(p, centroid);
        dfs2(centroid, centroid, level[centroid]);
        for(Integer e : adj[centroid]) {
            if(deleted[e]) continue;
                deleted[e] = true;
            int w = adj(centroid, e);
            decompose(w, centroid);
        }
    } 

    static void dfs2(int u, int p, int lvl) {
        for(Integer e : adj[u]) {
            int w = adj(u, e);
            if(w == p || deleted[e]) continue;
            dist[lvl][w] = dist[lvl][u] + 1;
            dfs2(w, u, lvl);
        }
    }

    static int adj(int x, int e) { return U[e] ^ V[e] ^ x; }

    static int find_centroid(int u, int p) {
        for(Integer e : adj[u]) {
            if(deleted[e]) continue;
            int w = adj(u, e);
            if(w != p && sub[w] > nn / 2) return find_centroid(w, u);
        }
        return u;
    }

    static void add_edge_centroid_tree(int parent, int child) {
        par[child] = parent;
        level[child] = level[parent] + 1;
    }

    static void dfs1(int u, int p) {
        sub[u] = 1;
        nn++;
        for(Integer e : adj[u]) {
            int w = adj(u, e);
            if(w != p && !deleted[e]) {
                dfs1(w, u);
                sub[u] += sub[w];
            }
        }
    }
}