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.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE_KsyshaIDerevo solver = new TaskE_KsyshaIDerevo();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE_KsyshaIDerevo {

    public static final int BUBEN = 333;

    Graph g;
    boolean[] colored;
    int[] q;
    int n;
    int[] dst;
    private LCA lca;
    int[] way;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        g = new Graph();
        n = in.nextInt();
        g.initGraph(n, n-1);
        int countQ = in.nextInt();
        for (int i = 0; i < n-1; ++i) {
            int a = in.nextInt();
            int b = in.nextInt();
            g.addEdge(a-1, b-1);
        }
        colored = new boolean[n];
        colored[0] = true;
        q = new int[n];
        dst = new int[n];
        way = new int[n];
        dump();

        lca = new LCA(g, 0, Parent.run(g, 0));
        dfs(0, -1, 0);
        List<Integer> add = new ArrayList<Integer>();

        for (int i = 0, mi = 0; i < countQ; ++i, ++mi) {
            if (mi == BUBEN) {
                mi = 0;
                dump();
                add.clear();
            }
            int type = in.nextInt();
            int v = in.nextInt()-1;
            if (type == 1) {
                add.add(v);
                colored[v] = true;
            } else {
                int res = dst[v];
                for (int u : add) {
                    res = Math.min(res, getDst(u, v));
                }
                out.println(res);
            }
        }
    }

    int getDst(int v, int u) {
        return way[v] + way[u] - 2 * way[lca.LCA(v, u)];
    }

    void dfs(int v, int p, int w) {
        way[v] = w;
        for (int ei = g.first[v]; ei != -1; ei = g.next[ei]) {
            int to = g.to[ei];
            if (to == p) continue;
            dfs(to, v, w + 1);
        }
    }

    private void dump() {
        int qSize = 0;
        for (int i = 0; i < n; ++i) {
            dst[i] = Integer.MAX_VALUE;
            if (colored[i]) {
                q[qSize++] = i;
                dst[i] = 0;
            }
        }
        for (int qi = 0; qi < qSize; ++qi) {
            int v = q[qi];
            for (int ei = g.first[v]; ei != -1; ei = g.next[ei]) {
                int to = g.to[ei];
                if (dst[to] > dst[v] + 1) {
                    dst[to] = dst[v] + 1;
                    q[qSize++] = to;
                }
            }
        }
    }
}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int nVertex;
    public int nEdges;
    public int curEdge;

    public Graph() {}

    public void initGraph(int n, int m) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        Arrays.fill(first, -1);
    }

    public void addEdge(int a, int b) {
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        ++curEdge;

        next[curEdge] = first[b];
        first[b] = curEdge;
        to[curEdge] = a;
        from[curEdge] = b;
        ++curEdge;
    }

}

class LCA {
    public int[] height;
    public int[] dfsOrder;
    public int[] posInDfsOrder;
    public int countDfsOrder;
    private int block;
    private int[][] blockTable;
    int logMaxList;
    int[] blockHash;
    int[][][] blockRmq;
    int[] log2;
    int[] parent;
    int n;

    public LCA(Graph tree, int root, int[] parent) {
        n = tree.nVertex;
        log2 = new int[2 * n];
        height = new int[n];
        Arrays.fill(height, -1);
        dfsOrder = new int[n*2-1];
        posInDfsOrder = new int[n];
        countDfsOrder = 0;
        this.parent = parent;
        dfsStack(tree, root);
        logMaxList = log(countDfsOrder);
        buildLCA();
    }

    // Walk graph
    private void dfsStack(Graph tree, int v) {
        int[] stackVertex = new int[tree.nVertex*2];
        int[] stackHeight = new int[tree.nVertex*2];
        int[] stackEdge = new int[tree.nVertex*2];
        int top = 0;
        stackHeight[top] = 0;
        stackVertex[top] = v;
        stackEdge[top] = tree.first[v];
        ++top;
        int currentHeight, edge;
        while (top > 0) {
            --top;
            v = stackVertex[top];
            currentHeight = stackHeight[top];
            edge = stackEdge[top];

            if (height[v] == -1) {
                height[v] = currentHeight;
                posInDfsOrder[v] = countDfsOrder;
                dfsOrder[countDfsOrder++] = v;
            } else {
                dfsOrder[countDfsOrder++] = v;
            }

            if (edge == -1) continue;

            int nextEdge = tree.next[edge];

            if (nextEdge != -1) {
                if (tree.to[nextEdge] == parent[v]) {
                    nextEdge = tree.next[nextEdge];
                }
            }

            stackHeight[top] = currentHeight;
            stackVertex[top] = v;
            stackEdge[top] = nextEdge;
            ++top;

            int u = tree.to[edge];
            stackHeight[top] = currentHeight + 1;
            stackVertex[top] = u;
            int edgeId = tree.first[u];
            if (edgeId != -1) {
                if (tree.to[edgeId] == v) {
                    edgeId = tree.next[edgeId];
                }
            }
            stackEdge[top] = edgeId;
            ++top;
        }
    }

    int log(int n) {
        int res = 1;
        while ((1 << res) < n)  ++res;
        return res;
    }

    // compares two indices in a
    int minHeight(int i, int j) {
        return height[dfsOrder[i]] < height[dfsOrder[j]] ? i : j;
    }

    // O(N) preprocessing
    void buildLCA() {
        block = (logMaxList + 1) / 2;
        int blocks = countDfsOrder / block + ((countDfsOrder % block > 0) ? 1 : 0);
        int maxBlocks = ((2 * n) / block) + 2;
        blockHash = new int[maxBlocks + 1];
        blockTable = new int[maxBlocks + 1][logMaxList + 1];
        blockRmq = new int[(int) (Math.sqrt(2*n) + 2)][block + 2][block + 2];
        ArrayUtils.fill(blockRmq, -1);
        ArrayUtils.fill(blockTable, -1);
        Arrays.fill(blockHash, 0);

        // precalc in each block and build sparse table
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (blockTable[blockId][0] == -1 || minHeight(i, blockTable[blockId][0]) == i) {
                blockTable[blockId][0] = i;
            }
        }

        for (int j = 1; j <= logMaxList; ++j) {
            for (int i = 0; i < blocks; ++i) {
                int ni = i + (1 << (j - 1));
                if (ni >= blocks) {
                    blockTable[i][j] = blockTable[i][j - 1];
                } else {
                    blockTable[i][j] = minHeight(blockTable[i][j - 1], blockTable[ni][j - 1]);
                }
            }
        }

        // calc hashes of blocks
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder || j < block; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (j > 0 && (i >= countDfsOrder || minHeight(i - 1, i) == i - 1)) {
                blockHash[blockId] += (1 << (j - 1));
            }
        }

        // precalc RMQ inside each unique block
        for (int i = 0; i < blocks; ++i) {
            int id = blockHash[i];
            if (blockRmq[id][0][0] != -1) continue;
            for (int l = 0; l < block; ++l) {
                blockRmq[id][l][l] = l;
                for (int r = l + 1; r < block; ++r) {
                    blockRmq[id][l][r] = blockRmq[id][l][r-1];
                    if (i * block + r < countDfsOrder) {
                        blockRmq[id][l][r] = minHeight(i * block + blockRmq[id][l][r], i * block + r) - i * block;
                    }
                }
            }
        }

        // precalc logarithms
        for (int i = 0, j = 0; i < countDfsOrder; ++i) {
            if (1 << (j + 1) <= i) ++j;
            log2[i] = j;
        }
    }

    // answers RMQ in block #bl [l;r] in O(1)
    int LCAInBlocks(int blockId, int l, int r) {
        return blockRmq[blockHash[blockId]][l][r] + blockId * block;
    }

    // answers LCA in O(1)
    public int LCA(int v, int u) {
        int l = posInDfsOrder[v], r = posInDfsOrder[u];
        if (l > r) {
            int t = l;
            l = r;
            r = t;
        }
        int leftBlock = l / block, rightBlock = r / block;
        if (leftBlock == rightBlock) {
            return dfsOrder[LCAInBlocks(leftBlock, l % block, r % block)];
        }
        int ans1 = LCAInBlocks(leftBlock, l % block, block - 1);
        int ans2 = LCAInBlocks(rightBlock, 0, r % block);
        int ans = minHeight(ans1, ans2);
        if (leftBlock < rightBlock - 1) {
            int pw2 = log2[rightBlock-leftBlock-1];
            int ans3 = blockTable[leftBlock + 1][pw2];
            int ans4 = blockTable[rightBlock - (1 << pw2)][pw2];
            ans = minHeight(ans, minHeight(ans3, ans4));
        }
        return dfsOrder[ans];
    }

    // End of LCA
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Parent {
    public static int[] run(Graph tree, int root) {
        int[] parent = new int[tree.nVertex];
        int[] queue = new int[tree.nVertex];
        int front = 0, back = 0;
        queue[back++] = root;
        parent[root] = -1;
        while (front < back) {
            int v = queue[front++];
            for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                if (parent[v] != tree.to[i]) {
                    queue[back++] = tree.to[i];
                    parent[tree.to[i]] = v;
                }
            }
        }
        return parent;
    }

}

class ArrayUtils {

    public static void fill(int[][] f, int value) {
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], value);
        }
    }

    public static void fill(int[][][] a, int value) {
        for (int i = 0; i < a.length; ++i) {
            fill(a[i], value);
        }
    }

}

