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
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author dipankar12
 */
import java.io.*;
import java.util.*;
public class r199e {
    static ArrayList<Integer> adj[];
    static int centroidtree[],subsize[],level[],lca[][],near[];
    
    static int findsize(int src,int p)
    {
        int sz=1;
        for(int i:adj[src])
        {
            if(i!=p&&centroidtree[i]==-2)
            {
                sz+=findsize(i,src);
            }
        }
        return subsize[src]=sz;
    }
    static int decompose(int src,int p,int n,int lb)
    {
        if(p==-1)
            n=findsize(src,-1);
        
        int idx=-1;
        for(int i:adj[src])
        {
            if(i!=p&&centroidtree[i]==-2&&subsize[i]>n/2)
            {
                idx=i;
                break;
            }
        }
        
        //System.out.println("centroid id"+idx);
        //on the basis of centroid
        if(idx!=-1)
            return decompose(idx,src,n,lb);
        
        //now decompose forest
        centroidtree[src]=-1;
        for(int i:adj[src])
            if(centroidtree[i]==-2)
                centroidtree[decompose(i,-1,n,lb+1)]=src;
        level[src]=lb;
        return src;
    }
    static void computedist(int lb,int src,int p,int d)
    {
        lca[lb][src]=d;
        for(int i:adj[src])
        {
            if(i!=p&&level[i]>=lb)
                computedist(lb,i,src,d+1);
        }
    }
    
    //update
    static void update(int v)
    {
        int u=v,lb=level[v];
        while(u!=-1)
        {
            //System.out.println("u "+u);
            near[u]=Math.min(near[u],lca[lb][v]);
            //System.out.println("near u is"+near[u]);
            u=centroidtree[u];
            --lb;
        }
    }
    static int query(int v)
    {
        int ans=(int)1e+9,u=v,lb=level[u];
        while(u!=-1)
        {
            ans=Math.min(ans, near[u]+lca[lb][v]);
            u=centroidtree[u];
            --lb;
        }
        return ans;
    }
    public static void main(String args[])
    {
        fastio in=new fastio(System.in);
        PrintWriter pw=new PrintWriter(System.out);

        int n=in.nextInt();
        int m=in.nextInt();
        
        adj=new ArrayList[n+1];
        for(int i=0;i<=n;i++)
            adj[i]=new ArrayList<Integer>();
        
        lca=new int[18][n+1];
        near=new int[n+1];
        centroidtree=new int[n+1];
        Arrays.fill(centroidtree, -2);
        subsize=new int[n+1];
        level=new int[n+1];
        
        for(int i=0;i<n-1;i++)
        {
            int u=in.nextInt();
            int v=in.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }
        
        decompose(1,-1,n,0);
        for(int i=1;i<=n;i++)
            computedist(level[i],i,-1,0);
        
        Arrays.fill(near, n);
        update(1);
        //pw.println("near");
        //for(int i=1;i<=n;i++)
            //pw.print(near[i]+" ");
        //pw.println();
        
        for(int i=0;i<m;i++)
        {
            if(in.nextInt()==1)
                update(in.nextInt());
            else
                pw.println(query(in.nextInt()));
        }
        
        //pw.println("centroid tree");
        //for(int i=1;i<=n;i++)
            //pw.print(centroidtree[i]+" ");
        //pw.println();
        pw.close();
    }

    static class fastio {
     
            private final InputStream stream;
            private final byte[] buf = new byte[8192];
            private int cchar, snchar;
            private SpaceCharFilter filter;
     
            public fastio(InputStream stream) {
                this.stream = stream;
            }
     
            public int nxt() {
                if (snchar == -1)
                    throw new InputMismatchException();
                if (cchar >= snchar) {
                    cchar = 0;
                    try {
                        snchar = stream.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (snchar <= 0)
                        return -1;
                }
                return buf[cchar++];
            }
     
            public int nextInt() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = nxt();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = nxt();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
     
            public long nextLong() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = nxt();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = nxt();
                } 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 String readString() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = nxt();
                } while (!isSpaceChar(c));
                return res.toString();
            }
     
            public String nextLine() {
                int c = nxt();
                while (isSpaceChar(c))
                    c = nxt();
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = nxt();
                } 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);
            }
        }
    

}
