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



public class Solution {

    
class Node {
    int depth, id, subtreeSize;
    HashSet<Integer> edge = new HashSet<>();
    int parent;
    Node centroidParent;

    Node(int id) {
        this.id = id;
    }
}


/*
LCA using sparse-table
 */
class LCA {
    private Node[] nodes;
    private int[][] table;
    int root, logval = 25, nodecount;

    public LCA(Node[] nodes, int root) {
        this.nodes = nodes;
        this.root = root;
        nodecount = nodes.length;
        initDFS(root, root, 0);
        initLCA();
    }

    //set parent and depth of each node
    private void initDFS(int curr, int parent, int depth) {
        nodes[curr].parent = parent;
        nodes[curr].depth = depth;
        for (int child : nodes[curr].edge) {
            if (child != parent) {
                initDFS(child, curr, depth + 1);
            }
        }
    }

    private void initLCA() {
        table = new int[nodecount][logval];
        for (int[] row : table) {
            Arrays.fill(row, -1);
        }
        //set closest parent to each node in the sparse table
        for (int i = 0; i < nodecount; i++) {
            table[i][0] = nodes[i].parent;
        }
        /* Setting parents.
        Example : If the 8th parent of node 'i' is identified,
        The 16th parent of node 'i' is the 8th parent of the 8th parent of 'i'.
         */
        for (int j = 1; j < logval; j++) {
            for (int i = 0; i < nodecount; i++) {
                if (table[i][j - 1] != -1) {
                    table[i][j] = table[table[i][j - 1]][j - 1];
                }
            }
        }
    }


    int queryLCA(int u, int v) {
        //we need node references by 'v' to be the deepest
        if (nodes[v].depth < nodes[u].depth) {
            int tmp = v;
            v = u;
            u = tmp;
        }
        int diff = nodes[v].depth - nodes[u].depth;
        for (int i = 0; i < logval; i++) {
            if (((diff >> i) & 1) > 0) {
                v = table[v][i];
            }
        }
        if (u == v)
            return u;
        for (int i = logval - 1; i >= 0; i--) {
            if (table[u][i] != table[v][i]) {
                u = table[u][i];
                v = table[v][i];
            }
        }
        return table[u][0];
    }
}


class CentroidDecomposition {

    Node[] nodes;

    CentroidDecomposition(Node[] nodes) {
        this.nodes = nodes;
        build(null, nodes[0]);
    }

    private void build(Node parent, Node curr) {

        int n = setSubTreeSizeDFS(parent, curr);
        Node centroid = findCentroidDFS(parent, curr, n / 2);
        if (parent == null) {
            parent = centroid;
        }
        centroid.centroidParent = parent;

        for (int c : centroid.edge) {
            Node child = nodes[c];
            if (child != centroid) {
                child.edge.remove(centroid.id);
                build(centroid, child);
            }
        }
    }

    private Node findCentroidDFS(Node parent, Node curr, int halfTree) {
        for (int c : curr.edge) {
            Node child = nodes[c];
            if (child != parent && child.subtreeSize > halfTree) {
                return findCentroidDFS(curr, child, halfTree);
            }
        }
        return curr;
    }

    private int setSubTreeSizeDFS(Node parent, Node curr) {
        curr.subtreeSize = 1;
        for (int c : curr.edge) {
            Node child = nodes[c];
            if (child != parent) {
                curr.subtreeSize += setSubTreeSizeDFS(curr, child);
            }
        }
        return curr.subtreeSize;
    }
}

    int n, q;
    int infinity = 1000000000;
    Kattio io = new Kattio(System.in, System.out);
    Node[] nodes;
    int[] answer;
    LCA lca;
    CentroidDecomposition centroidDecomposition;
    ArrayList<Integer> results = new ArrayList<>();

    Solution() {
        n = io.getInt();
        q = io.getInt();
        answer = new int[n];
        nodes = new Node[n];
        Arrays.fill(answer,infinity);

        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 1; i < n; i++) {
            int from = io.getInt() - 1;
            int to = io.getInt() - 1;
            nodes[from].edge.add(to);
            nodes[to].edge.add(from);
        }
        lca = new LCA(nodes, 0);
        centroidDecomposition = new CentroidDecomposition(nodes);
        update(0);
        for (int i = 0; i < q; i++) {
            int type = io.getInt();
            int val = io.getInt()-1;
            if (type == 1) {
                update(val);
            } else {
                io.println(query(val));
            }
        }
        io.close();
    }

    void update(int curr) {
        answer[curr] = 0;
        updateHelper(nodes[curr], curr);

        /*
        System.out.println("Distance array after update of "+(curr+1));
        for(int i=1; i<=n; i++){
            System.out.println(" Node "+i+" with distance "+answer[i-1]);
        }
        System.out.println();
        */
    }


    void updateHelper(Node curr, int startingNode){
        int distance = getDistance(curr.id, startingNode);
        answer[curr.id] = Math.min(answer[curr.id], distance);
        if(curr.centroidParent != curr){
            updateHelper(curr.centroidParent, startingNode);
        }
    }


    int getDistance(int a, int b){
        int lcaOfAandB = lca.queryLCA(a,b);
        return nodes[a].depth + nodes[b].depth - (nodes[lcaOfAandB].depth*2);
    }

    int query(int curr) {
        int lowestDist = answer[curr];
        return queryHelper(nodes[curr], curr, lowestDist);
    }

    private int queryHelper(Node curr, int startingNode, int lowestDist) {
        int distance = getDistance(curr.id, startingNode);
        //System.out.println("distance between "+(curr.id+1)+" and "+(startingNode+1)+" is "+distance);
        int ld = Math.min(lowestDist, distance + answer[curr.id]);
        if(curr.centroidParent != curr){
            return queryHelper(curr.centroidParent, startingNode, ld);
        }
        return ld;
    }


    public static void main(String[] args) {
        new Solution();
    }

}


/**
 * Simple yet moderately fast I/O routines.
 * <p>
 * Example usage:
 * <p>
 * Kattio io = new Kattio(System.in, System.out);
 * <p>
 * while (io.hasMoreTokens()) {
 * int n = io.getInt();
 * double d = io.getDouble();
 * double ans = d*n;
 * <p>
 * io.println("Answer: " + ans);
 * }
 * <p>
 * io.close();
 * <p>
 * <p>
 * Some notes:
 * <p>
 * - When done, you should always do io.close() or io.flush() on the
 * Kattio-instance, otherwise, you may lose output.
 * <p>
 * - The getInt(), getDouble(), and getLong() methods will throw an
 * exception if there is no more data in the input, so it is generally
 * a good idea to use hasMoreTokens() to check for end-of-file.
 *
 * @author: Kattis
 */

class Kattio extends PrintWriter {
    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

    public String getLine() {
        try {
            return r.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }


    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}