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

/**
 *
 * @author umang
 *
 */

public class ProblemE{

    public static int mod = (int) (1e9+7);
    public static InputReader in;
    public static PrintWriter out;
    public static ArrayList<Integer>[] g;
    public static int len;
    public static int[][] up;
    public static int[] tin;
    public static int[] tout;
    public static int time;
    public static int[] depth;
    public static int[] dis;
    public static int[] tmp;
    public static int[] buf;
    public static int cnt;
    
    public static void dfs(int u, int p,int level) {
      depth[u]=level;
      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 :g[u])
        if (v != p)
          dfs( v, u,level+1);
      tout[u] = time++;
    }

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

    public static 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];
    }

    public static void preprocess(int n,int root){

      len = 1;
      while ((1 << len) <= n) ++len;
      up = new int[len][n];
      tin = new int[n];
      tout = new int[n];
      dis = new int[n];
      depth = new int[n];
      dfs(root, root,0);
    }
    
    public static int distance(int a,int b){
        return depth[a]+depth[b]-2*depth[lca(a,b)];
    }
    
    public static void bfs(){
        Queue<Integer> q=new ArrayDeque<>();
        for(int i=0;i<=cnt;i++){
            dis[buf[i]]=0;
            q.add(buf[i]);
            buf[i]=0;
        }
        while(!q.isEmpty()){
            int x=q.peek();
            q.poll();
            for(int v:g[x]){
                if(dis[v]>dis[x]+1){
                    dis[v]=dis[x]+1;
                    q.add(v);
                }
            }
        }
    }
    
    public static void main(String[] args) {

        in = new InputReader(System.in);
        out = new PrintWriter(System.out);

        int n=in.nextInt();
        int m=in.nextInt();
        g=new ArrayList[n];
        for(int i=0;i<n;i++) g[i]=new ArrayList<>();
        
        for(int i=0;i<n-1;i++){
            int a=in.nextInt()-1;
            int b=in.nextInt()-1;
            g[a].add(b);
            g[b].add(a);
        }
        preprocess(n, 0);
        Arrays.fill(dis, Integer.MAX_VALUE);
        int sq=310;
        buf=new int[sq+1];
        cnt=0;
        while(m-->0){
            int t=in.nextInt();
            int u=in.nextInt()-1;
            if(t==1){
                buf[++cnt]=u;
                if(cnt==sq){
                    bfs();
                    cnt=0;
                }
            }
            else{
                int ans=dis[u];
                for(int i=0;i<=cnt;i++){
                    ans=min(ans,distance(u, buf[i]));
                }
                out.println(ans);
            }
        }
        
        out.close();
    }

    static class Pair implements Comparable<Pair>{

        char c;
        int x,i;
        long y;
        long k;
        Pair (char c,int x,long y){
            this.c=c;
            this.x=x;
            this.y=y;
        }

        public int compareTo(Pair o) {
                    return Long.compare(this.x,o.x);
        }

        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y == y && p.k==k;
            }
            return false;
        }


        @Override
        public String toString() {
            return  "("+x + " " + y +" "+k+" "+i+" )";
        }

    } 

    public static long add(long x, long y) {
	return (x + y)%mod;
    }
    
    public static long mul(long x, long y) {
	return (x*y)%mod;
    }
    
    public static boolean isPal(String s){
        for(int i=0, j=s.length()-1;i<=j;i++,j--){
                if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    public static String rev(String s){
            StringBuilder sb=new StringBuilder(s);
            sb.reverse();
            return sb.toString();
    }

    public static long gcd(long x,long y){
    if(x%y==0)
            return y;
    else
            return gcd(y,x%y);
    }

    public static int gcd(int x,int y){
    if(x%y==0)
            return y;
    else 
            return gcd(y,x%y);
    }

    public static long gcdExtended(long a,long b,long[] x){

        if(a==0){
            x[0]=0;
            x[1]=1;
            return b;
        }
        long[] y=new long[2];
        long gcd=gcdExtended(b%a, a, y);

        x[0]=y[1]-(b/a)*y[0];
        x[1]=y[0];

        return gcd;
    }

    public static int abs(int a,int b){
    return (int)Math.abs(a-b);
    }

    public static long abs(long a,long b){
    return (long)Math.abs(a-b);
    }

    public static int max(int a,int b){
    if(a>b)
            return a;
    else
            return b;
    }

    public static int min(int a,int b){
    if(a>b)
            return b;
    else 
            return a;
    }

    public static long max(long a,long b){
    if(a>b)
            return a;
    else
            return b;
    }

    public static long min(long a,long b){
    if(a>b)
            return b;
    else 
            return a;
    }

    public static long pow(long n,long p,long m){
     long  result = 1;
      if(p==0)
        return 1;
    if (p==1)
        return n;
    while(p!=0)
    {
        if(p%2==1)
            result *= n;
        if(result>=m)
        result%=m;
        p >>=1;
        n*=n;
        if(n>=m)
        n%=m;
    }
    return result;
    }

    public static long pow(long n,long p){
    long  result = 1;
      if(p==0)
        return 1;
    if (p==1)
        return n;
    while(p!=0)
    {
        if(p%2==1)
            result *= n;	    
        p >>=1;
        n*=n;	    
    }
    return result;
    }
     public static void debug(Object... o) {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader {

            private final InputStream stream;
            private final byte[] buf = new byte[8192];
            private int curChar, 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 int[] nextIntArray(int n) {
                    int a[] = new int[n];
                    for (int i = 0; i < n; i++) {
                            a[i] = nextInt();
                    }
                    return a;
            }

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

            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 String nextLine() {
                    int c = snext();
                    while (isSpaceChar(c))
                            c = snext();
                    StringBuilder res = new StringBuilder();
                    do {
                            res.appendCodePoint(c);
                            c = snext();
                    } while (!isEndOfLine(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;
            }

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

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