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;
int n;
vector<vector<int> > g;
namespace LCA {
vector<vector<int> > up;
vector<int> depth;
const int LG = 18;
void dfs(int u, int p) {
  depth[u] = (p == -1) ? 0 : depth[p] + 1;
  for (int bit = 1; bit < LG; bit++) {
    int v = up[u][bit - 1];
    if (v == -1) break;
    up[u][bit] = up[v][bit - 1];
  }
  for (auto v : g[u]) {
    if (v == p) continue;
    up[v][0] = u;
    dfs(v, u);
  }
}
void init() {
  up = vector<vector<int> >(n + 1, vector<int>(LG, -1));
  depth = vector<int>(n + 1);
  dfs(1, -1);
}
int walk(int u, int k) {
  for (int bit = 0; bit < LG; bit++) {
    if ((k >> bit) & 1) {
      u = up[u][bit];
    }
  }
  return u;
}
int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  u = walk(u, depth[u] - depth[v]);
  if (u == v) return u;
  for (int bit = LG - 1; bit >= 0; bit--) {
    if (up[u][bit] != up[v][bit]) {
      u = up[u][bit];
      v = up[v][bit];
    }
  }
  return up[u][0];
}
int dis(int u, int v) {
  int p = lca(u, v);
  return depth[u] + depth[v] - 2 * depth[p];
}
};  // namespace LCA
namespace CD {
vector<bool> blocked;
vector<int> ss;
vector<int> pa;
void find_size(int u, int p) {
  ss[u] = 1;
  for (auto v : g[u]) {
    if (v == p or blocked[v]) continue;
    find_size(v, u);
    ss[u] += ss[v];
  }
}
int find_centroid(int u, int p, const int n) {
  for (auto v : g[u]) {
    if (v == p) continue;
    if (not blocked[v] and ss[v] > n / 2) {
      return find_centroid(v, u, n);
    }
  }
  return u;
}
void decomposition(int u, int p) {
  find_size(u, p);
  int c = find_centroid(u, -1, ss[u]);
  blocked[c] = true;
  pa[c] = p;
  for (auto v : g[c]) {
    if (blocked[v]) continue;
    decomposition(v, c);
  }
}
void init() {
  ss = vector<int>(n + 1);
  pa = vector<int>(n + 1);
  blocked = vector<bool>(n + 1, false);
  decomposition(1, -1);
  ss.clear();
  blocked.clear();
}
};  // namespace CD
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> n >> q;
  g = vector<vector<int> >(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  CD::init();
  LCA::init();
  const int INF = 1e9;
  vector<int> ans(n + 1, INF);
  auto update = [&](int u) {
    ans[u] = 0;
    int v = u;
    while (CD::pa[v] != -1) {
      v = CD::pa[v];
      ans[v] = min(ans[v], LCA::dis(u, v));
    }
  };
  auto query = [&](int u) {
    int ret = ans[u];
    int v = u;
    while (CD::pa[v] != -1) {
      v = CD::pa[v];
      ret = min(ret, LCA::dis(u, v) + ans[v]);
    }
    return ret;
  };
  update(1);
  while (q--) {
    int t, u;
    cin >> t >> u;
    if (t == 1) update(u);
    if (t == 2) cout << query(u) << '\n';
  }
  return (0);
}
