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.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String args[]) throws Exception {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i, j,x,y;
        int n=in.nextInt();
        int q=in.nextInt();
        ArrayList<Integer> tree[]=new ArrayList[n];
        for(i=0;i<n;i++){
            tree[i]=new ArrayList<>();
        }
        for(i=0;i<n-1;i++){
            x=in.nextInt()-1;
            y=in.nextInt()-1;
            tree[x].add(y);
            tree[y].add(x);
        }
        CentroidDecomposition cd=new CentroidDecomposition(tree,n,0);
        long ans[]=new long[n];
        Arrays.fill(ans,Integer.MAX_VALUE);
        x=0;
        while(true){
            ans[x]=Math.min(ans[x],cd.dist(0,x));
            if(cd.par[x]==x)
                break;
            x=cd.par[x];
        }
        while(q-->0){
            x=in.nextInt();
            int u=in.nextInt()-1;
            if(x==1){
                int v=u;
                while(true){
                    ans[v]=Math.min(ans[v],cd.dist(u,v));
                    if(cd.par[v]==v)
                        break;
                    v=cd.par[v];

                }
            }
            else{
               long an=Integer.MAX_VALUE;
               int v=u;
               while(true){
                   an=Math.min(an,ans[v]+cd.dist(u,v));
                   if(cd.par[v]==v)
                       break;
                   v=cd.par[v];
               }
               sb.append(an).append("\n");
            }
        }
        System.out.println(sb);
    }
}

class CentroidDecomposition {
    private int N, MLOG;
    private ArrayList<Integer> tree[];
    int  par[],lev[],sub[];
    private int sptable[][];
    private boolean remove[];
    private int nn;

    public CentroidDecomposition(ArrayList<Integer> itree[], int n, int root) {
        N = n;
        tree = new ArrayList[N];
        for (int i = 0; i < n; i++)
            tree[i] = new ArrayList<>(itree[i]);
        par = new int[N];
        lev = new int[N];
        sub = new int[N];
        remove=new boolean[N];
        preprocess(root);
        decompose(root,-1);
    }
    public void preprocess(int root){
        int u = 1;
        MLOG = 1;
        while (u < N) {
            u = u * 2;
            MLOG++;
        }

        sptable = new int[N][MLOG];
        dfs0(root, -1);

        for (int i = 0; i < N; i++) {
            for (int j = 1; j < MLOG; j++)
                sptable[i][j] = -1;
        }

        for (int i = 1; i < MLOG; i++) {
            for (int j = 0; j < N; j++) {
                if (sptable[j][i - 1] != -1) {
                    sptable[j][i] = sptable[sptable[j][i - 1]][i - 1];
                }
            }
        }
    }

    public void dfs0(int u, int p) {

        sptable[u][0]=p;
        for (int v : tree[u]) {
            if (v != p) {
                lev[v] = lev[u] + 1;
                dfs0(v, u);
            }
        }
    }

    public int lca(int u, int v) {
        if (lev[u] < lev[v]) {
            int t = u;
            u = v;
            v = t;
        }

        int dist = lev[u] - lev[v];
        for(int i=0;i<MLOG;i++){
            if((dist & (1<<i))>0)
                u=sptable[u][i];
        }

        if(u==v)
            return u;

        for(int j=MLOG-1;j>=0;j--){
            if(sptable[u][j]!=-1 && (sptable[u][j]!=sptable[v][j])) {
                u = sptable[u][j]; v=sptable[v][j];
            }
        }
        return sptable[u][0];
    }
    public int dist(int u,int v){
        return lev[u]+lev[v]-2*lev[lca(u,v)];
    }
    public void decompose(int root,int p){
        nn=0;
        dfs1(root,root);
        int centroid=dfs2(root,root);
        remove[centroid]=true;
        if(p==-1)
            p=centroid;
        par[centroid]=p;

        for(int v:tree[centroid]){
            if(!remove[v])
                decompose(v,centroid);
        }

    }
    public void dfs1(int u,int p){
        sub[u]=1;
        nn++;
        for(int v:tree[u]){
            if(v!=p && !remove[p]){
                dfs1(v,u);
                sub[u]+=sub[v];
            }
        }
    }

    public int dfs2(int u,int p){
        for(int v:tree[u]){
            if(v!=p && !remove[v] && sub[v]>(nn/2))
                return dfs2(v,u);
        }
        return u;
    }
}


class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}