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.*;
import java.io.*;
public class E
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String[] l = input.readLine().split(" ");
        int n = Integer.parseInt(l[0]);
        int m = Integer.parseInt(l[1]);
        Tree tree = Tree.read(input, n);
        tree.lcaEnable();
        tree.centroidEnable();
        tree.decompose(0, -1);
        int[] closest = new int[n];
        for (int i = 0; i < n; i++) closest[i] = 100000;
        update(tree, closest, 0);
        for (int i = 0; i < m; i++)
        {
            l = input.readLine().split(" ");
            int a = Integer.parseInt(l[1]) - 1;
            if (l[0].equals("1")) update(tree, closest, a);
            else System.out.println(query(tree, closest, a));
        }
    }
    public static int query(Tree tree, int[] closest, int i)
    {
        int j = i;
        int result = Integer.MAX_VALUE;
        while (true)
        {
            result = Math.min(result, closest[j] + tree.distance(j, i));
            if (j == tree.centroidParent[j]) break;
            j = tree.centroidParent[j];
        }
        return result;
    }
    public static void update(Tree tree, int[] closest, int i)
    {
        int j = i;
        while (true)
        {
            closest[j] = Math.min(closest[j], tree.distance(j, i));
            if (j == tree.centroidParent[j]) break;
            j = tree.centroidParent[j];
        }
    }
}
class Tree
{
    public HashSet<Integer>[] adj;
    public int[][] parent;
    public int[] centroidParent;
    public int[] level;
    public int[] size;

    public Tree(HashSet<Integer>[] adj)
    {
        this.adj = adj;
    }
    public static Tree read(BufferedReader input, int n) throws IOException
    {
        HashSet<Integer>[] adj = new HashSet[n];
        for (int i = 0; i < n; i++) adj[i] = new HashSet<Integer>();
        for (int i = 0; i < n - 1; i++)
        {
            String[] l = input.readLine().split(" ");
            int a = Integer.parseInt(l[0]) - 1;
            int b = Integer.parseInt(l[1]) - 1;
            adj[a].add(b);
            adj[b].add(a);
        }
        return new Tree(adj);
    }
    public void lcaEnable()
    {
        parent = new int[(int)(Math.log(adj.length) / Math.log(2) + 2)][adj.length];
        level = new int[adj.length];
        dfsParent(0);
        for (int i = 1; i < parent.length; i++)
            for (int j = 0; j < parent[0].length; j++)
                parent[i][j] = parent[i - 1][parent[i - 1][j]];
    }
    public void centroidEnable()
    {
        size = new int[adj.length];
        centroidParent = new int[adj.length];
    }
    public void dfsParent(int i)
    {
        for (int j : adj[i])
            if (j != parent[0][i])
            {
                parent[0][j] = i;
                level[j] = level[i] + 1;
                dfsParent(j);
            }
    }
    public int lca(int a, int b)
    {
        if (level[b] < level[a])
        {
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
        }
        int d = level[b] - level[a];
        for (int i = 0; i < parent.length; i++)
            if (((d >> i) & 1) == 1) b = parent[i][b];
        if (a == b) return a;
        for (int i = parent.length - 1; i >= 0; i--)
            if (parent[i][a] != parent[i][b])
            {
                a = parent[i][a];
                b = parent[i][b];
            }
        return parent[0][a];
    }
    public int distance(int a, int b)
    {
        return level[a] + level[b] - 2 * level[lca(a, b)];
    }
    public void dfsSize(int i, int p)
    {
        size[i] = 1;
        for (int j : adj[i])
            if (j != p)
            {
                dfsSize(j, i);
                size[i] += size[j];
            }
    }
    public int centroid(int i, int p, int half)
    {
        for (int j : adj[i])
            if (j != p && size[j] > half) return centroid(j, i, half);
        return i;
    }
    public void decompose(int i, int p)
    {
        dfsSize(i, i);
        int c = centroid(i, p, size[i] / 2);
        if (p == -1) p = c;
        centroidParent[c] = p;
        for (int j : adj[c])
        {
            adj[j].remove(c);
            decompose(j, c);
        }
        adj[c].clear();
    }
}