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 javax.swing.border.*;
import java.io.*;
import java.math.BigDecimal;
import java.util.*;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;

public class Main {

    void run(){
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        try{
            if( oj ){
                br  = new BufferedReader(new InputStreamReader(System.in  ) );
                out = new PrintWriter(   new OutputStreamWriter(System.out) );
            } else{
                br  = new BufferedReader(new FileReader("k3.in"));
                out = new PrintWriter(   new FileWriter("k3.out") );
            }
        } catch (IOException e) {
            System.exit(-1);
        }
        long tB = System.currentTimeMillis();
        solve();
//        out.println( "Time: " + (System.currentTimeMillis()-tB)/1e3 );
        out.flush();
    }

    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

    String next(){
        try {
            while( in==null || !in.hasMoreTokens() )
                in = new StringTokenizer( br.readLine() );
        } catch (IOException e) {
            System.exit(-1);
        }
        return in.nextToken();
    }

    int nextInt(){
        return Integer.parseInt(next());
    }

    long nextLong(){
        return Long.parseLong(next());
    }

    BigInteger nextBigInteger(){
        return new BigInteger(next());
    }

    double nextDouble(){
        return Double.parseDouble(next());
    }

    public static void main(String[] args){
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "myThread", 1L<<29 ).start();
    }



    void TLE(){ for(;;); }

    void MLE(){
        int[][] adj = new int[1024*1024][];
        for( int i = 0; i < adj.length; ++i )
            adj[i] = new int[1024*1024];
    }

    void exit( int val ){
        out.flush();
        System.exit(val);
    }

    int n, m;
    int[][] gr;
    int szOrd;
    int[] ord, h, posOrd;
    int[][] lca;
    int[] clr;
    final int red = 0, blue = 1, inf = (int)1e8;
    int[] dist;

    int[] Q = new int[400_000];
    void bfs(){
        dist = new int[n+1];
        fill(dist,inf);
        //Deque<Integer> Q = new ArrayDeque<>();
        int pos=0, sz=0;
        for( int v = 1; v <= n; ++v )
            if( clr[v] == red ){
                //Q.add( v );
                Q[sz++] = v;
                dist[v] = 0;
            }
        //while( !Q.isEmpty() ){
        while( pos < sz ){
            //int v = Q.pollFirst();
            int v = Q[pos++];
            for( int to : gr[v] ){
                if( dist[to] > dist[v] + 1 ){
                    dist[to] = dist[v] + 1;
//                    Q.addLast(to);
                    Q[sz++] = to;
                }
            }
        }
    }

    int log2(int val){ return 31 - Integer.numberOfLeadingZeros(val); }

    int[] arrLog2;
    int getLCA( int a, int b ){
        if( arrLog2 == null ){
            arrLog2 = new int[szOrd+1];
            for( int i = 0; i < arrLog2.length; ++i )
                arrLog2[i] = log2(i);
        }
        int l = min(posOrd[a],posOrd[b]);
        int r = max(posOrd[a],posOrd[b]);
//        int p = log2(r-l+1);
        int p = arrLog2[r-l+1];
        return minByH( lca[l][p], lca[r-(1<<p)+1][p] );
    }

    int minByH(int a, int b){ return h[a] < h[b]? a : b; }

    void dfs(int v, int pr){
        posOrd[v] = szOrd;
        for( int to : gr[v] ){
            if( to == pr ) continue;
            ord[szOrd++] = v;
            h[to] = h[v] + 1;
            dfs(to,v);
        }
        ord[szOrd++] = v;
    }

    void solve(){
        {
            n = nextInt();
            m = nextInt();
            Vector<Integer>[] grgr = new Vector[n+1];
            for( int v = 1; v <= n; ++v )
                grgr[v] = new Vector<>();
            for( int j = 0; j < n-1; ++j ){
                int a = nextInt();
                int b = nextInt();
                grgr[a].add(b);
                grgr[b].add(a);
            }
            gr = new int[n+1][];
            for( int v = 1; v <= n; ++v ){
                gr[v] = new int[grgr[v].size()];
                for( int j = 0; j < grgr[v].size(); ++j )
                    gr[v][j] = grgr[v].get(j);
            }
        }


        ord = new int[4*n];
        h = new int[n+1];
        posOrd = new int[4*n];
        dfs(1,-1);

        final int maxP = log2(szOrd)+1;
        lca = new int[szOrd+1][maxP+1];
        for( int p = 0; p <= maxP; ++p )
        for( int l = 0; l < szOrd; ++l ){
            if( p == 0 ) lca[l][p] = ord[l];
            else if( l+(1<<p)-1 < szOrd )
                lca[l][p] = minByH( lca[l][p-1], lca[l+(1<<(p-1))][p-1] );
        }

        clr = new int[n+1];
        fill(clr,blue);
        clr[1] = red;
        //
        int sqrtM = (int)sqrt(m);//////!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        int posVer=-100;
        int[] ver = new int[sqrtM];
        for( int i = 0; i < m; ++i ){
            if( i%sqrtM==0 ){
                bfs();
                posVer = 0;
            }
            //
            int t = nextInt();
            int v = nextInt();
            if( t == 1 ){
                clr[v] = red;
                ver[posVer++] = v;
            }
            else{
                int cur = inf;
                for( int j = 0; j < posVer; ++j ){
                    int to = ver[j];
                    cur = min(cur,h[v] + h[to] - 2*h[getLCA(v,to)]);
                }
                out.println( min( dist[v], cur ) );
            }
            /**/
        }

        return;
    }



}