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>
using namespace std;
const int INF = 1e7;
template <class V, class E>
struct Graph {
  int sz;
  vector<V> v;
  vector<vector<E>> e;
  Graph(int n) : sz(n), v(n), e(n) {}
  template <class... Args>
  inline void assign_vertex(int pos, Args... args) {
    v[pos] = V(args...);
  }
  template <class... Args>
  inline void add_edge(int pos, Args... args) {
    e[pos].emplace_back(args...);
  }
  inline int size() { return sz; }
};
struct Vertex {
  int dist;
  Vertex() : dist(INF) {}
};
using vertex = Vertex;
struct Edge {
  int to;
  Edge(int t) : to(t) {}
  Edge() {}
};
using edge = Edge;
using graph = Graph<vertex, edge>;
template <class G>
struct LCA {
  int sz;
  vector<vector<int>> dp;
  vector<int> depth;
  int log2_n;
  LCA(G& g, int root) : sz(g.size()), depth(sz, -100000) {
    log2_n = 0;
    for (int t = sz; t; t /= 2, log2_n++)
      ;
    dp.resize(log2_n, vector<int>(sz, -1));
    dfs(g, root);
    for (int i = 1; i < log2_n; i++) {
      for (int j = 0; j < sz; j++) {
        if (dp[i - 1][j] == -1)
          dp[i][j] = -1;
        else
          dp[i][j] = dp[i - 1][dp[i - 1][j]];
      }
    }
  }
  inline int size() { return sz; }
  void dfs(G& g, int root) {
    stack<tuple<int, int, int>> s;
    s.emplace(root, -1, 0);
    while (!s.empty()) {
      int now, par, d;
      tie(now, par, d) = s.top();
      s.pop();
      dp[0][now] = par;
      depth[now] = d;
      for (auto& x : g.e[now]) {
        if (x.to != par) s.emplace(x.to, now, d + 1);
      }
    }
  }
  int get(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = log2_n - 1; i >= 0; i--) {
      if (((depth[b] - depth[a]) >> i) & 1) b = dp[i][b];
    }
    if (a == b) return a;
    for (int i = log2_n - 1; i >= 0; i--) {
      if (dp[i][a] != dp[i][b]) {
        a = dp[i][a];
        b = dp[i][b];
      }
    }
    return dp[0][a];
  }
  int distace(int a, int b) {
    return depth[a] + depth[b] - 2 * depth[get(a, b)];
  }
};
using lca = LCA<graph>;
struct Centroid : public graph {
  vector<bool> dead;
  vector<int> subsize;
  vector<int> par;
  vector<vector<edge>> child_par;
  vector<vector<edge>> par_child;
  Centroid(int n)
      : graph(n),
        dead(sz, false),
        subsize(sz, sz),
        par(sz, -1),
        child_par(n),
        par_child(n) {}
  void centroid_dfs(int v, int chsize, vector<int>& res, int p = -1) {
    stack<int> s;
    stack<int> st;
    st.push(v);
    map<int, int> ok;
    par[v] = -1;
    while (!st.empty()) {
      auto t = st.top();
      st.pop();
      subsize[t] = 1;
      s.push(t);
      ok[t] = 1;
      for (auto& x : e[t]) {
        if (dead[x.to] || par[t] == x.to) continue;
        par[x.to] = t;
        st.push(x.to);
      }
    }
    while (!s.empty()) {
      auto t = s.top();
      s.pop();
      if (par[t] != -1) {
        subsize[par[t]] += subsize[t];
        if (subsize[t] > chsize / 2) {
          ok[par[t]] = 0;
        }
      }
    }
    for (auto& o : ok) {
      if (o.second && (chsize + 1) / 2 <= subsize[o.first]) {
        res.push_back(o.first);
      }
    }
  }
  int build(int root = 0) {
    vector<int> next;
    int r = find(root, next);
    for (auto& x : next) {
      int t = build(x);
      par_child[r].emplace_back(t);
      child_par[t].emplace_back(r);
    }
    return r;
  }
  int find(int root, vector<int>& next_root) {
    vector<int> centroids;
    centroid_dfs(root, subsize[root], centroids);
    int centor = centroids[0];
    if (par[centor] >= 0)
      subsize[par[centor]] = subsize[root] - subsize[centor];
    dead[centor] = true;
    for (auto& x : e[centor]) {
      if (dead[x.to]) continue;
      next_root.emplace_back(x.to);
    }
    return centor;
  }
  void paint(lca& L, int x) {
    v[x].dist = 0;
    int now = x;
    while (child_par[now].size()) {
      now = child_par[now][0].to;
      v[now].dist = min(v[now].dist, L.distace(x, now));
    }
  }
  int calc(lca& L, int x) {
    int res = v[x].dist;
    int now = x;
    while (child_par[now].size()) {
      now = child_par[now][0].to;
      res = min(res, v[now].dist + L.distace(x, now));
    }
    return res;
  }
};
using centroid = Centroid;
int main() {
  int N, Q;
  cin >> N >> Q;
  centroid C(N);
  graph G(N);
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    C.add_edge(a, b);
    C.add_edge(b, a);
    G.add_edge(a, b);
    G.add_edge(b, a);
  }
  lca L(G, 0);
  C.build();
  C.paint(L, 0);
  for (int i = 0; i < Q; i++) {
    int a, b;
    cin >> a >> b;
    b--;
    if (a == 1) {
      C.paint(L, b);
    } else {
      cout << C.calc(L, b) << endl;
    }
  }
}
