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
import java.io.*;
import java.util.*;
public class A
{
    /********************  Pre-processing  ************************/
    private static int tin[], tout[], timer=0,N, logN, anc[][], depth[];
    private static HashSet<Integer> edge[];

    private static int[] sub,par,ans,D[];
    private static final int INF=(int)(1e8);

    private static void DFS0(int u, int p) //Making LCA array
    {
        tin[u]=timer++;
        anc[u][0]=p;

        for(int i=1;i<=logN;i++)
            anc[u][i]=anc[anc[u][i-1]][i-1];

        for(int v:edge[u])
        {
            if(v==p) continue;
            depth[v]=depth[u]+1;
            DFS0(v,u);
        }

        tout[u]=timer++;
    }
    private static boolean isAncestor(int u, int v)
    {
        return tin[u]<=tin[v]&&tout[v]<=tout[u];
    }
    private static int LCA(int u, int v)
    {
        if(isAncestor(u,v)) return u;
        if(isAncestor(v,u)) return v;

        for(int i=logN;i>=0;i--)
        {
            if (!isAncestor(anc[u][i], v))
                u = anc[u][i];
        }
        return anc[u][0];
    }
    private static int dist(int u, int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
    /********************  Decomposition  ************************/
    private static int NN;
    private static void DFS1(int u, int p) //subtree size
    {
        sub[u]=1; NN++;
        for(int v:edge[u])
        {
            if(v==p) continue;
            DFS1(v,u); sub[u]+=sub[v];
        }
    }
    private static int find_centroid(int u, int p) //find centroid of this component
    {
        for(int v:edge[u])
        {
            if(v==p) continue;
            if(sub[v]>NN/2) return find_centroid(v,u);
        }
        return u;
    }
    private static void decompose(int u, int p)
    {
        NN=0;
        DFS1(u,u);
        int centroid=find_centroid(u,u);
        if(p==-1) p=centroid;
        par[centroid]=p;
        for(int v:edge[centroid])
        {
            edge[v].remove(centroid);
            decompose(v,centroid);
        }
    }
    /********************  Queries  ************************/
    private static void update(int u)
    {
        int x=u,lev=0;
        while (true)
        {
            ans[x]=Math.min(ans[x],D[u][lev++]);
            if(x==par[x]) break;
            x=par[x];
        }
    }
    private static int query(int u)
    {
        int ret=INF,x=u,lev=0;
        while (true)
        {
            ret=Math.min(ret,D[u][lev++]+ans[x]);
            if(x==par[x]) break;
            x=par[x];
        }
        return ret;
    }
    private static void formD()
    {
        for(int u=0;u<N;u++)
        {
            int x=u,lev=0;
            while (true)
            {
                D[u][lev++]=dist(u,x);
                if(x==par[x]) break;
                x=par[x];
            }
        }
    }
    private static void init()
    {
        logN=Integer.numberOfTrailingZeros(Integer.highestOneBit(N));
        tin=new int[N]; tout=new int[N];
        anc=new int[N][logN+1]; depth=new int[N];
        sub=new int[N]; par=new int[N];
        ans=new int[N]; Arrays.fill(ans,INF);
        D=new int[N][logN+1];
    }
    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 HashSet[N]; for(i=0;i<N;i++) edge[i]=new HashSet<>();
        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);
        }

        init();
        DFS0(0,0);
        decompose(0,-1);
        formD();
        update(0);

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

            if(t==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();}
    }
}