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.lang.reflect.Array;
import java.util.*;
import java.io.*;

public class Main
{
    static int [][] adjList ;
    static int [] parent  ;
    static int [][] P;
    static int [] L  ;
    static int [] ans ;
    static int N ;
    static int K = 20 ;
    static int [] size ;
    static int [] depth ;
    static final int INF = (int)1e9 ;

    static void dfs(int u , int p)
    {
        P[0][u] = p ;

        for(int v : adjList[u])
            if(v != p)
            {
                L[v] = L[u] + 1 ;
                dfs(v , u);
            }
    }

    static void preprocess()
    {
        P = new int [K + 1][N] ;
        L = new int [N] ;
        for(int i = 0 ; i <= K ; i++)Arrays.fill(P[i] , -1);

        dfs(0 , - 1);

        for(int k = 1 ; k <= K ; k++)
            for(int i = 0 ; i < N ; i++)
                if(P[k - 1][i] != -1)
                    P[k][i] = P[k - 1][P[k - 1][i]] ;
    }
    static int LCA(int p , int q)
    {
        if(L[p] < L[q]){p ^= q ; q ^= p ; p ^= q ;}

        int remDist = L[p] - L[q] ;

        for(int i = K ; i >= 0 ; i--)
            if((remDist & (1 << i)) != 0)
                p = P[i][p] ;

        if(p == q)return p ;

        for(int i = K ; i >= 0 ; i--)
            if(P[i][p] != -1 && P[i][p] !=  P[i][q])
            {
                p = P[i][p] ; q = P[i][q] ;
            }
        return P[0][p] ;
    }
    static int getDist(int u , int v)
    {
        return L[u] + L[v] - (L[LCA(u , v)] << 1) ;
    }
    static int getSize(int u , int p)
    {
        size[u] = 1 ;

        for(int v : adjList[u])
            if(v != p && depth[v] == -1)
                size[u] += getSize(v , u) ;

        return size[u] ;
    }

    static int getCentroid(int u , int p , int n)
    {
       for(int v : adjList[u])
           if(v != p && depth[v] == -1 && size[v] * 2 > n)
               return getCentroid(v , u , n) ;
       return u ;
    }

    static int decompose(int u , int p , int lvl)
    {
        int centroid = getCentroid(u , -1 , getSize(u , -1)) ;

        depth[centroid] = lvl ;

        for(int v : adjList[centroid])
            if(depth[v] == -1)
                parent[decompose(v , -1 , lvl + 1)] = centroid ;
        return centroid ;
    }
    static void update(int u)
    {
        int original = u ;

        while(u != -1)
        {
            ans[u] = Math.min(ans[u] , getDist(original , u)) ;
            u = parent[u] ;
        }
    }
    static int query(int u)
    {
        int original = u ;
        int ret = INF ;
        while(u != -1)
        {
            ret = Math.min(ret , getDist(original , u) + ans[u]) ;
            u = parent[u] ;
        }
        return ret ;
    }
    public static void main (String [] args) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = sc.nextInt() , m = sc.nextInt() ;
        N = n ;
        int [] x = new int [n - 1] , y = new int [n - 1] , deg = new int [n] ;
        parent = new int [n] ;
        size = new int [n] ;
        depth = new int [n] ; Arrays.fill(depth , -1);
        ans = new int [n] ; Arrays.fill(ans , INF);
        for(int i = 0 ;i < n - 1 ; i++)
        {
            deg[x[i] = sc.nextInt() - 1] ++;
            deg[y[i] = sc.nextInt() - 1] ++;
        }
        adjList = new int [n][] ;
        for(int i = 0 ; i < n ;i++) adjList[i] = new int [deg[i]]  ;

        for(int i = 0 ; i < n - 1; i++)
        {
            adjList[x[i]][--deg[x[i]]] = y[i] ;
            adjList[y[i]][--deg[y[i]]] = x[i] ;
        }
        preprocess();

        parent[decompose(0 , -1 , 0)] = -1 ;
        update(0);

        while(m-->0)
            if(sc.nextInt() == 1)
                update(sc.nextInt() - 1);
            else
                out.println(query(sc.nextInt() - 1));
        out.flush();
        out.close();
    }


    static class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

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

}