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.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int m = in.nextInt();
        TreeBlock tree = new TreeBlock(n, m);
        for (int i = 1; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            tree.addEdge(a, b);
        }
        tree.init();
        for (int i = 0; i < m; i++) {
            int t = in.nextInt();
            int v = in.nextInt();
            if (t == 1) {
                tree.set(v);
            } else {
                System.out.println(tree.query(v));
            }
        }
    }
}

class TreeBlock {
    private int n, m;
    private List<Node> link;
    private int[] dist;
    private Queue<Integer> queue;
    private List<Integer> seq;
    private List<Integer> depth;
    private int[] firstIndex;
    private int[][] min;

    private int operations;
    private int threshold;

    private static class Node {
        int v;
        Node next;
        Node(int v) {
            this.v = v;
        }
    }

    public TreeBlock(int n, int m) {
        this.n = n;
        this.m = m;
        this.link = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            link.add(new Node(0));
        }
    }

    public void addEdge(int i, int j) {
        addLink(i, j);
        addLink(j, i);
    }

    public void init() {
        dist = new int[n + 1];
        Arrays.fill(dist, n);
        dist[1] = 0;

        queue = new ArrayDeque<>();
        queue.offer(1);
        bfs();

        seq = new ArrayList<>();
        depth = new ArrayList<>();
        firstIndex = new int[n + 1];
        dfs(1, 0, new boolean[n + 1]);

        int maxK = (int) (Math.log(seq.size()) / Math.log(2));
        min = new int[seq.size()][maxK+1];
        for (int i = 0; i < seq.size(); i++) {
            min[i][0] = seq.get(i);
        }
        for (int k = 1; k <= maxK; k++) {
            for (int i = seq.size() - (1 << k); i >= 0; i--) {
                if (getDepth(min[i][k-1])
                        < getDepth(min[i + (1 << (k - 1))][k-1])) {
                    min[i][k] = min[i][k-1];
                } else {
                    min[i][k] = min[i + (1 << (k - 1))][k-1];
                }
            }
        }

        threshold = (int) Math.sqrt(m);
    }

    public void set(int i) {
        dist[i] = 0;
        queue.offer(i);

        updateOperation();
    }

    public int query(int i) {
        int min = dist[i];

        for (int v: queue) {
            int lca = LCA(i, v);
            min = Math.min(min, getDepth(i) + getDepth(v) - getDepth(lca) * 2);
        }

        updateOperation();

        return min;
    }

    private void addLink(int from, int to) {
        Node newNode = new Node(to);
        newNode.next = link.get(from).next;
        link.get(from).next = newNode;
    }

    private void dfs(int i, int dep, boolean[] vis) {
        firstIndex[i] = seq.size();
        seq.add(i);
        depth.add(dep);
        vis[i] = true;
        for (Node cur = link.get(i).next; cur != null; cur = cur.next) {
            if (!vis[cur.v]) {
                dfs(cur.v, dep + 1, vis);
                seq.add(i);
                depth.add(dep);
            }
        }
    }

    private void bfs() {
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (Node cur = link.get(x).next; cur != null; cur = cur.next) {
                if (dist[x] + 1 < dist[cur.v]) {
                    dist[cur.v] = dist[x] + 1;
                    queue.offer(cur.v);
                }
            }
        }
    }

    private int getDepth(int i) {
        return depth.get(firstIndex[i]);
    }

    private int LCA(int u, int v) {
        int iu = firstIndex[u], iv = firstIndex[v];
        if (iu > iv) {
            return LCA(v, u);
        }
        int l = iv - iu + 1, k = 0;
        for (; (1 << (k + 1)) <= l; k++);


        if (getDepth(min[iu][k]) < getDepth(min[iv - (1 << k) + 1][k])) {
            return min[iu][k];
        } else {
            return min[iv - (1 << k) + 1][k];
        }
    }

    private void updateOperation() {
        operations++;
        if (operations > threshold) {
            bfs();
            threshold += (int) Math.sqrt(m);
        }
    }
}