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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
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);
    XeniaAndTree solver = new XeniaAndTree();
    solver.solve(1, in, out);
    out.close();
  }

  static class XeniaAndTree {

    List<Integer>[] g;
    int n;
    int[][] parent;
    int[] depth;
    int[] ans;
    int[] centroidPar;
    int[] subTreeSize;
    boolean[] removed;
    int log;
    XeniaTreeSolver solver;
    CentroidComposer<Integer> composer = (a, b) -> 0;

    void dfs(int cur, int p) {
      for (int nxt : g[cur]) {
        if (nxt != p) {
          depth[nxt] = depth[cur] + 1;
          parent[0][nxt] = cur;
          dfs(nxt, cur);
        }
      }
    }

    void initialize() {
      dfs(1, 0);
      for (int i = 1; i < log; i++) {
        for (int j = 1; j <= n; j++) {
          parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
      }
    }

    int lca(int a, int b) {
      if (depth[a] > depth[b]) {
        int temp = a;
        a = b;
        b = temp;
      }
      int diff = depth[b] - depth[a];
      for (int i = 0; i < log && diff > 0; i++) {
        if ((diff & (1 << i)) > 0) {
          b = parent[i][b];
          Bits.unset(diff, i);
        }
      }
      if (a == b) {
        return b;
      }
      if (depth[a] != depth[b]) {
        throw new RuntimeException();
      }
      for (int i = log - 1; i >= 0; i--) {
        if (parent[i][a] != parent[i][b]) {
          a = parent[i][a];
          b = parent[i][b];
        }
      }
      return parent[0][a];
    }

    int distance(int a, int b) {
      return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }

    void update(int u) {
      int cur = u;
      while (cur > 0) {
        ans[cur] = Math.min(ans[cur], distance(cur, u));
        cur = solver.parent[cur];
      }
    }

    int query(int u) {
      int cur = u;
      int val = 1 << 30;
      while (cur > 0) {
        val = Math.min(val, ans[cur] + distance(cur, u));
        cur = solver.parent[cur];
      }
      return val;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      n = in.nextInt();
      int m = in.nextInt();
      int cur = 1;
      centroidPar = new int[n + 1];
      removed = new boolean[n + 1];
      ans = new int[n + 1];
      subTreeSize = new int[n + 1];
      while (cur <= n) {
        ++log;
        cur <<= 1;
      }
      parent = new int[log][n + 1];
      depth = new int[n + 1];
      g = GraphUtils.generateGraph(n + 1);
      for (int i = 0; i < n - 1; i++) {
        int a = in.nextInt();
        int b = in.nextInt();
        g[a].add(b);
        g[b].add(a);
      }

      initialize();

      solver = new XeniaTreeSolver(n + 1);

      CentroidTemplate<Integer> template = new CentroidTemplate<>(g, n + 1, solver, composer);

      template.solve(1, 0);

      Arrays.fill(ans, 1 << 30);

      update(1);

      for (int i = 0; i < m; i++) {
        int t = in.nextInt();
        int v = in.nextInt();
        if (t == 1) {
          update(v);
        } else {
          out.println(query(v));
        }
      }
    }

    class XeniaTreeSolver implements CentroidSolver<Integer> {

      int[] parent;

      public XeniaTreeSolver(int n) {
        parent = new int[n];
      }

      public Integer work(List<Integer>[] tree, int n, int centroid, int centroidParent,
          boolean[] removed,
          int[] subTreeSize) {
        parent[centroid] = centroidParent;
        return 0;
      }

    }

  }

  static interface CentroidSolver<T> {

    T work(List<Integer>[] tree, int n, int centroid, int centroidParent, boolean[] removed,
        int[] subTreeSize);

  }

  static interface CentroidComposer<T> {

    T compose(T a, T b);

  }

  static final class Bits {

    private Bits() {
      throw new UnsupportedOperationException("cannot instantiate Bits class");
    }

    public static int unset(int mask, int k) {
      return (mask & ~(1 << k));
    }

  }

  static class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 13];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == -1) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return -1;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    }

  }

  static class GraphUtils {

    private GraphUtils() {
    }

    public static List<Integer>[] generateGraph(int n) {
      List<Integer>[] graph = new ArrayList[n];
      for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<>();
      }
      return graph;
    }

  }

  static class CentroidTemplate<T> {

    List<Integer>[] tree;
    boolean[] removed;
    int[] subTreeSize;
    int[] depth;
    int n;
    CentroidSolver<T> solver;
    CentroidComposer<T> composer;

    public CentroidTemplate(List<Integer>[] tree, int n, CentroidSolver<T> solver,
        CentroidComposer<T> composer) {
      this.solver = solver;
      this.n = n;
      this.tree = tree;
      removed = new boolean[n];
      subTreeSize = new int[n];
      depth = new int[n];
      this.composer = composer;
    }

    public T solve(int root, int parent) {
      computeSubtreeSize(root, parent);
      int centroid = findCentroid(root, parent, subTreeSize[root]);
      T result = solver.work(tree, n, centroid, parent,
          removed, subTreeSize);
      removed[centroid] = true;
      for (int u : tree[centroid]) {
        if (u == parent || removed[u]) {
          continue;
        }
        result = composer.compose(result, solve(u, centroid));
      }
      return result;
    }

    int findCentroid(int cur, int par, int comp) {
      for (int nxt : tree[cur]) {
        if (nxt == par || removed[nxt]) {
          continue;
        }
        if (subTreeSize[nxt] > comp / 2) {
          return findCentroid(nxt, cur, comp);
        }
      }
      return cur;
    }

    private void computeSubtreeSize(int u, int p) {
      subTreeSize[u] = 1;
      for (int nxt : tree[u]) {
        if (nxt == p || removed[nxt]) {
          continue;
        }
        computeSubtreeSize(nxt, u);
        subTreeSize[u] += subTreeSize[nxt];
      }
    }

  }
}

