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
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

        int n;
        Set<Integer>[] edges;
        List<Integer>[] centroidDistance;
        List<Integer>[] centroids;
        int[] centroidParent;
        int[] centroidSize;
        int[] queue;
        int[] visit;
        void bfs(int centroid) {
            int start = 0, end = 0;
            queue[end++] = centroid;
            visit[centroid] = 0;
            centroidDistance[centroid].add(0);
            centroids[centroid].add(centroid);
            while (start < end) {
                int u = queue[start++];
                int d = visit[u];
                for (int v: edges[u]) if (visit[v] == -1) {
                    queue[end++] = v;
                    visit[v] = d + 1;
                    centroidDistance[v].add(d + 1);
                    centroids[v].add(centroid);
                }
            }
            for (int i = 0; i < end; i++) visit[queue[i]] = -1;
            if (centroidSize[centroid] != end) {
                throw new RuntimeException();
            }
        }

        int findCentroid(int u, int p, int n1) {
            int cnt = 1;
            boolean goodCenter = true;
            for (int v : edges[u]) {
                if (v == p) continue;
                int res = findCentroid(v, u, n1);
                if (res >= 0)
                    return res;
                int size = -res;
                goodCenter &= size <= n1 / 2;
                cnt += size;
            }
            goodCenter &= n1 - cnt <= n1 / 2;
            return goodCenter ? u : -cnt;
        }

        int dfsSize(int u, int p) {
            int s = 1;
            for (int v: edges[u]) if (v != p) s += dfsSize(v, u);
            return s;
        }

        void centroidDecomposition(int u, int p) {
            edges[u].remove(p);
            int size = dfsSize(u, p);
            int centroid = findCentroid(u, p, size);
            centroidParent[centroid] = p;
            centroidSize[centroid] = size;
            bfs(centroid);
            for (int v: edges[centroid]) {
                centroidDecomposition(v, centroid);
            }
        }

        void update(int u) {
            int s = centroids[u].size();
            for (int i = 0; i < s; i++) {
                int d = centroidDistance[u].get(i);
                int c = centroids[u].get(i);
                minimumDistanceToRed[c] = Math.min(minimumDistanceToRed[c], d);
            }
        }

        int[] minimumDistanceToRed;

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            int q = sc.nextInt();
            edges = new Set[n];
            centroidDistance = new List[n];
            centroids = new List[n];
            for (int i = 0; i < n; i++) {
                edges[i] = new HashSet<>();
                centroidDistance[i] = new ArrayList<>();
                centroids[i] = new ArrayList<>();
            }
            centroidParent = new int[n];
            centroidSize = new int[n];
            queue = new int[n];
            visit = new int[n];
            Arrays.fill(visit, -1);
            minimumDistanceToRed = new int[n];
            Arrays.fill(minimumDistanceToRed, Integer.MAX_VALUE / 2);
            for (int i = 0; i < n - 1; i++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                edges[a].add(b);
                edges[b].add(a);
            }
            centroidDecomposition(0, -1);
            update(0);
            for (int i = 0; i < q; i++) {
                int t = sc.nextInt();
                int u = sc.nextInt() - 1;
                if (t == 1) update(u);
                else {
                    int mind = Integer.MAX_VALUE / 2;
                    int s = centroids[u].size();
                    for (int j = 0; j < s; j++) {
                        int c = centroids[u].get(j);
                        int d = centroidDistance[u].get(j);
                        mind = Math.min(mind, d + minimumDistanceToRed[c]);
                    }
                    pw.println(mind);
                }
            }
        }
    }

    static long TIME_START, TIME_END;


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("input"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("input"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

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

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}