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
//created by Whiplash99
//Testing sparse table implementation speed, for LCA
//Inspired by spar5h 's implementation: https://codeforces.com/contest/342/submission/39889700
import java.io.*;
import java.util.*;
public class C
{
    /******************** Pre-Processing *******************/
    private static int height[], first[], sparse[][], N, logN, K;
    private static ArrayList<Integer> euler, edge[];

    private static void DFS(int u, int p)
    {
        first[u]=euler.size(); euler.add(u);
        for(int v:edge[u])
        {
            if(v==p) continue;
            height[v]=height[u]+1;
            DFS(v,u); euler.add(u);
        }
    }
    private static void build()
    {
        for(int i=0;i<euler.size();i++) sparse[i][0]=euler.get(i);
        for(int j=1;j<=K;j++)
        {
            for(int i=0;i+(1<<j)<=euler.size();i++)
            {
                int x=sparse[i][j-1];
                int y=sparse[i+(1<<(j-1))][j-1];
                sparse[i][j]=(height[x]<height[y])?x:y;
            }
        }
    }
    private static int RMQ(int l, int r)
    {
        int j=getLog(r-l+1);
        int x=sparse[l][j];
        int y=sparse[r-(1<<j)+1][j];
        return (height[x]<height[y])?x:y;
    }
    private static int LCA(int u, int v)
    {
        int left=first[u], right=first[v];
        if(left>right){int tmp=left; left=right; right=tmp;}
        return RMQ(left,right);
    }
    private static int getLog(int a)
    {
        return Integer.numberOfTrailingZeros(Integer.highestOneBit(a));
    }
    private static void initLCA()
    {
        logN=getLog(N);
        height=new int[N]; first=new int[N]; euler=new ArrayList<>();
        DFS(0,0); K=getLog(euler.size());
        sparse=new int[euler.size()][K+1];
    }
    private static int dist(int u, int v){return height[u]+height[v]-2*height[LCA(u,v)];}
    /*********************** Decomposition **************************/
    private static int[] par, size;
    private static boolean[] found;

    private static int DFS2(int u, int p)
    {
        size[u]=1;
        for(int v:edge[u])
        {
            if(v==p||found[v]) continue;
            size[u]+=DFS2(v,u);
        }
        return size[u];
    }
    private static int getCentroid(int u, int p, int NN) //get the centroid of this component
    {
        for(int v:edge[u])
        {
            if(found[v]||v==p) continue;
            if(size[v]>NN/2) return getCentroid(v,u,NN);
        }
        return u;
    }
    private static void decompose(int u, int p)
    {
        u=getCentroid(u,-1,DFS2(u,u)); found[u]=true; par[u]=p;
        for(int v:edge[u]) if(!found[v]) decompose(v,u);
    }
    private static void initDecompo(){par=new int[N]; size=new int[N]; found=new boolean[N];}
    /********************* Queries *********************/
    private static int[] ans;
    private static final int INF=(int)1e8;
    private static void update(int u)
    {
        int p=u;
        while (p!=-1)
        {
            ans[p]=Math.min(ans[p], dist(u,p));
            p=par[p];
        }
    }
    private static int query(int u)
    {
        int p=u, ret=INF;
        while (p!=-1)
        {
            ret=Math.min(ret,ans[p]+dist(u,p));
            p=par[p];
        }
        return ret;
    }
    private static void initQuery()
    {
        ans=new int[N];
        Arrays.fill(ans,INF);
    }
    /*********************** Driver ************************/
    public static void main(String[] args) throws IOException
    {
        Reader r=new Reader();

        int i;

        N=r.nextInt();
        int Q=r.nextInt();
        StringBuilder sb=new StringBuilder();

        edge=new ArrayList[N]; for(i=0;i<N;i++) edge[i]=new ArrayList<>();
        for(i=0;i<N-1;i++)
        {
            int u=r.nextInt()-1;
            int v=r.nextInt()-1;

            edge[u].add(v); edge[v].add(u);
        }

        initLCA();
        build();

        initDecompo();
        decompose(0,-1);

        initQuery();
        update(0);

        while (Q-->0)
        {
            int type=r.nextInt();
            int u=r.nextInt()-1;

            if(type==1) update(u);
            else sb.append(query(u)).append("\n");
        }
        System.out.println(sb);
    }
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
        public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
    }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
    }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
    }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
    }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
    }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
    }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
    }public void close() throws IOException{if(din==null) return;din.close();}
    }
}