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;
vector<int> G[100005];
int pa[20][100005];
int depth[100005], dist[100005];
int n;
void dfs(int v, int p, int d) {
  pa[0][v] = p;
  depth[v] = d;
  dist[v] = depth[v] - 1;
  for (int i = 0; i < (int)G[v].size(); i++)
    if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}
void init(int V) {
  dfs(1, 0, 1);
  for (int k = 0; k + 1 < 20; k++) {
    for (int v = 1; v <= V; v++) {
      if (pa[k][v] < 0)
        pa[k + 1][v] = -1;
      else
        pa[k + 1][v] = pa[k][pa[k][v]];
    }
  }
}
int get(int v, int x) {
  for (int k = 0; k < 20; k++)
    if ((x >> k) & 1) v = pa[k][v];
  return v;
}
int lca(int u, int v) {
  if (depth[u] > depth[v]) swap(u, v);
  v = get(v, depth[v] - depth[u]);
  if (u == v) return u;
  for (int k = 20 - 1; k >= 0; k--) {
    if (pa[k][u] != pa[k][v]) {
      u = pa[k][u];
      v = pa[k][v];
    }
  }
  return pa[0][u];
}
int dis(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
int q[100005], cnt = 0, vis[100005];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  init(n);
  queue<int> que;
  auto solve = [&]() {
    while (que.size()) {
      int u = que.front();
      que.pop();
      for (auto v : G[u]) {
        if (dist[v] > dist[u] + 1) {
          dist[v] = dist[u] + 1;
          que.push(v);
        }
      }
    }
  };
  int base = sqrt(n) + 1;
  auto update = [&](int x) {
    if (vis[x]) return;
    vis[x] = 1, dist[x] = 0, q[++cnt] = x, que.push(x);
    if (cnt == base) {
      solve();
      cnt = 0;
    }
  };
  auto query = [&](int x) {
    int ans = dist[x];
    for (int i = 1; i <= cnt; i++) {
      ans = min(ans, dis(q[i], x));
    }
    return ans;
  };
  for (int i = 1; i <= m; i++) {
    int op, x;
    cin >> op >> x;
    if (op == 1) {
      update(x);
    } else {
      cout << query(x) << endl;
    }
  }
}
