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
#include <bits/stdc++.h>
constexpr int INF = 1e6;
std::ostream& operator<<(std::ostream& os, const std::vector<int>& vector) {
  os << '[';
  for (int i = 0; i < vector.size(); ++i) {
    if (i > 0) {
      os << ", ";
    }
    os << vector[i];
  }
  return os << ']';
}
class Tree {
  struct Node {
    bool visited = false;
    int centroid_parent_idx;
    int paint_dist = INF;
    int size, height;
    int time_in, time_out;
    std::vector<int> parents, adj;
    bool contains(const Node& node) const {
      return time_in <= node.time_in && node.time_out <= time_out;
    }
  };
  std::vector<Node> nodes_;
  int init_sizes(int idx, int parent_idx = -1) {
    auto& node = nodes_[idx];
    if (node.visited) {
      return 0;
    }
    node.size = 1;
    for (int i : node.adj) {
      if (i != parent_idx) {
        node.size += init_sizes(i, idx);
      }
    }
    return node.size;
  }
  int find_centroid_idx(int idx, int size, int parent_idx = -1) {
    for (int i : nodes_[idx].adj) {
      if (i != parent_idx && !nodes_[i].visited && size < 2 * nodes_[i].size) {
        return find_centroid_idx(i, size, idx);
      }
    }
    return idx;
  }
  void init_centroid(int idx, int prev_centroid_idx = -1) {
    auto& node = nodes_[idx];
    if (node.visited) {
      return;
    }
    init_sizes(idx);
    int centroid_idx = find_centroid_idx(idx, node.size);
    auto& centroid = nodes_[centroid_idx];
    centroid.visited = true;
    centroid.centroid_parent_idx = prev_centroid_idx;
    for (int i : centroid.adj) {
      init_centroid(i, centroid_idx);
    }
  }
  int init_lca(int idx, int height = 0, int time = 0, int parent_idx = -1) {
    auto& node = nodes_[idx];
    node.time_in = time;
    node.height = height;
    if (parent_idx != -1) {
      node.parents.push_back(parent_idx);
      for (int i = 0;; ++i) {
        const auto& p = nodes_[node.parents.back()];
        if (p.parents.size() <= i) {
          break;
        }
        node.parents.push_back(p.parents[i]);
      }
    }
    for (int i : node.adj) {
      if (i != parent_idx) {
        time = init_lca(i, height + 1, time + 1, idx) + 1;
      }
    }
    node.time_out = time;
    return time;
  }
  int find_lca_idx(int first_idx, int second_idx, bool debug = false) {
    const auto& first = nodes_[first_idx];
    const auto& second = nodes_[second_idx];
    if (debug) {
      std::cout << "first = " << first_idx << ' ' << first.height << ' '
                << first.time_in << ' ' << first.time_out << ' '
                << first.parents << '\n';
      std::cout << "second = " << second_idx << ' ' << second.height << ' '
                << second.time_in << ' ' << second.time_out << ' '
                << second.parents << '\n';
    }
    if (first.contains(second)) {
      return first_idx;
    }
    for (int i = first.parents.size() - 1; i >= 0; --i) {
      if (nodes_[first_idx].parents.size() <= i) {
        continue;
      }
      int idx = nodes_[first_idx].parents[i];
      if (debug) {
        std::cout << "next = " << idx << ' ' << nodes_[idx].height << ' '
                  << nodes_[idx].time_in << ' ' << nodes_[idx].time_out << ' '
                  << nodes_[idx].parents << '\n';
      }
      if (!nodes_[idx].contains(second)) {
        first_idx = idx;
        if (debug) {
          std::cout << "update\n";
        }
      }
    }
    return nodes_[first_idx].parents.front();
  }
  int get_dist(int first, int second) {
    int lca_idx = find_lca_idx(first, second);
    auto result = nodes_[first].height + nodes_[second].height -
                  2 * nodes_[lca_idx].height;
    if (result < 0) {
      find_lca_idx(first, second, true);
      std::cout << "lca = " << lca_idx << ' ' << nodes_[lca_idx].height << ' '
                << nodes_[lca_idx].time_in << ' ' << nodes_[lca_idx].time_out
                << ' ' << nodes_[lca_idx].parents << '\n';
      exit(0);
    }
    return result;
  }

 public:
  Tree(int node_count) : nodes_(node_count) {}
  void add_edge(int first, int second) {
    nodes_[first].adj.push_back(second);
    nodes_[second].adj.push_back(first);
  }
  void init() {
    init_centroid(0);
    init_lca(0);
    paint(0);
  }
  int compute_paint_dist(int idx) {
    int result = INF;
    int root = idx;
    while (root != -1) {
      const auto& node = nodes_[root];
      result = std::min(result, node.paint_dist + get_dist(root, idx));
      root = node.centroid_parent_idx;
    }
    return result;
  }
  void paint(int idx) {
    int root = idx;
    while (root != -1) {
      auto& node = nodes_[root];
      node.paint_dist = std::min(node.paint_dist, get_dist(root, idx));
      root = node.centroid_parent_idx;
    }
  }
};
int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int node_count, query_count;
  std::cin >> node_count >> query_count;
  Tree tree(node_count);
  for (int i = 1; i < node_count; ++i) {
    int first, second;
    std::cin >> first >> second;
    tree.add_edge(first - 1, second - 1);
  }
  tree.init();
  while (query_count-- > 0) {
    int cmd, idx;
    std::cin >> cmd >> idx;
    switch (cmd) {
      case 1:
        tree.paint(idx - 1);
        break;
      case 2:
        std::cout << tree.compute_paint_dist(idx - 1) << '\n';
        break;
    }
  }
  return 0;
}
