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 javafx.scene.control.IndexRange;

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Task3 {

    public static void main(String[] args) throws IOException {

        new Task3().solve();

    }

    //ArrayList<Integer>[] g;

    int mod = 1000000007;

    PrintWriter out;

    int n;
    int m;

    long inf = Long.MAX_VALUE;

    //int[][] g = new int[110][110];

    StringBuilder t = new StringBuilder();

    int max = 0;

    long base = (1L << 63);

    ArrayList<Integer>[] g;

    void solve() throws IOException {

        //Reader in = new Reader("in.txt");
        //out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        Reader in = new Reader();
        PrintWriter out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );

        //BufferedReader br = new BufferedReader( new FileReader("in.txt") );
        //BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );


        n = in.nextInt();
        int m = in.nextInt();

        g = new ArrayList[n];

        for (int i = 0; i < n; i++)
            g[i] = new ArrayList<>();

        for (int i = 0; i < n-1; i++)
        {
            int x = in.nextInt()-1;
            int y = in.nextInt()-1;

            g[x].add(y);
            g[y].add(x);
        }

        Arrays.fill(depth, -1);

        findCentroid(0, n, -1, 0);

        int root = 0;
        while (depth[root] > 0)
            root++;

        dfs2(root, root, 0);

        while (1 << lg <= n)
            lg++;

        Arrays.fill(ans, 1000000000);

        paint(0);

        //System.err.println(getLca(1, 1));

        for (int i = 0; i < m; i++) {

            int c = in.nextInt();
            int v = in.nextInt()-1;

            if (c == 1)
                paint(v);
            else
                out.println(get(v));

        }

        out.flush();
        out.close();
    }

    int[] depth = new int[100000];
    int[] parent = new int[100000];
    int[] dp = new int[100000];
    int[][] d = new int[20][100000];
    int[] ans = new int[100000];
    int center = -1;
    int lg = 1;

    int getLca(int a, int b) {

        if (dp[a] > dp[b]) {

            int t = a;
            a = b;
            b = t;
        }

        int k = dp[b] - dp[a];

        for (int i = lg; i >= 0; i--)
            if (1 << i <= k) {
                b = d[i][b];
                k -= (1 << i);
            }

        if (a == b)
            return a;

        for (int i = lg; i >= 0; i--)
            if (d[i][a] != d[i][b]) {

                a = d[i][a];
                b = d[i][b];
            }

        return d[0][a];
    }

    int getCenter(int a, int b) {

        while (depth[a] > depth[b])
            a = parent[a];

        while (depth[a] < depth[b])
            b = parent[b];

        while (a != b) {
            a = parent[a];
            b = parent[b];
        }

        return a;
    }

    int dist(int a, int b) {

        int lca = getCenter(a, b);

        return dp[a]+dp[b] - 2*dp[getLca(a, b)];
    }

    void findCentroid(int root, int size, int last, int h) {

        center = -1;
        dfs(root, -1, size);
        depth[center] = h;
        parent[center] = last;
        int cn = center;

        for (int u : g[center])
            if (depth[u] == -1)
                findCentroid(u, size/2, cn, h+1);
    }

    int dfs(int v, int p, int n) {

        int cnt = 1;
        for (int u : g[v])
            if (u != p && depth[u] == -1)
                cnt += dfs(u, v, n);

        if (center == -1 && (cnt*2 >= n || p == -1))
            center = v;

        return cnt;
    }

    void dfs2(int v, int p, int h) {

        dp[v] = h;
        d[0][v] = p;

        for (int i = 1; 1 << i <= n; i++)
            d[i][v] = d[i-1][d[i-1][v]];

        for (int u : g[v])
            if (u != p)
                dfs2(u, v, h+1);
    }

    void paint(int v) {

        int u = v;

        while (u != -1) {

            ans[u] = Math.min(ans[u], dist(u, v));
            u = parent[u];
        }
    }

    int get(int v) {

        int res = ans[v];
        int u = v;

        while (u != -1) {

            //System.err.println(u+" "+(dp[v] - dp[u]));

            res = Math.min(res, ans[u]+dist(u, v));
            u = parent[u];
        }

        return res;
    }

    long gcd(long a, long b) {

        if (b == 0)
            return a;

        return gcd(b, a%b);

    }


    class Item {

        int a;
        int b;
        int c;

        Item(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }

    class Pair implements Comparable<Pair>{

        int a;
        int b;
        int i;

        Pair(int a, int b, int i) {

            this.a = a;
            this.b = b;
            this.i = i;
        }

        public int compareTo(Pair p) {

            if (a > p.a)
                return 1;

            if (a < p.a)
                return -1;

            if (b > p.b)
                return 1;

            if (b < p.b)
                return -1;

            return 0;
        }

        //		@Override
        //		public boolean equals(Object o) {
        //			Pair p = (Pair) o;
        //			return a == p.a && b == p.b;
        //		}
        //
        //		@Override
        //		public int hashCode() {
        //			return Integer.valueOf(a).hashCode() + Integer.valueOf(b).hashCode();
        //		}

    }

    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

    }

}