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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
int T = 0;
vector<vector<int>> adj;
vector<int> in, up, down, siz, par, depth;
void init(int n) {
  adj.resize(n);
  in.resize(n);
  siz.resize(n);
  up.resize(n);
  par.resize(n);
  down.resize(n);
  depth.resize(n);
}
void pre_dfs(int v = 0, int p = -1, int d = 0) {
  depth[v] = d, siz[v] = 1, par[v] = p;
  up[v] = down[v] = v;
  for (int& u : adj[v]) {
    if (u == p) continue;
    pre_dfs(u, v, d + 1);
    siz[v] += siz[u];
    if (siz[u] > siz[adj[v][0]]) {
      swap(u, adj[v][0]);
    }
  }
}
void dfs_hld(int v = 0, int p = -1) {
  in[v] = T++;
  for (int u : adj[v]) {
    if (u == p) continue;
    if (u == adj[v][0]) up[u] = up[v];
    dfs_hld(u, v);
    if (u == adj[v][0]) down[v] = down[u];
  }
}
const int inf = 1e9 + 7;
struct seg_tree {
  vector<int> t;
  int n;
  seg_tree() {}
  int combine(int a, int b) { return min(a, b); }
  void init(int m) {
    n = m;
    t.assign(2 * n, inf);
  }
  void update(int p, int x) {
    for (p += n, t[p] = combine(t[p], x); p >>= 1;)
      t[p] = combine(t[p << 1], t[p << 1 | 1]);
  }
  int query(int l, int r) {
    int resl = inf, resr = inf;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = combine(resl, t[l++]);
      if (r & 1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr);
  }
};
seg_tree upv, downv;
void red(int v) {
  int d = 0, p;
  while (true) {
    upv.update(in[v], depth[down[v]] - depth[v] + d);
    downv.update(in[v], depth[v] - depth[up[v]] + d);
    p = par[up[v]];
    if (p == -1) break;
    d += depth[v] - depth[p];
    v = p;
  }
}
int nearest(int v) {
  int ret = inf, d = 0, p;
  while (true) {
    int q = upv.query(in[up[v]], in[v]);
    q -= depth[down[v]] - depth[v];
    int w = downv.query(in[v], in[down[v]]);
    w -= depth[v] - depth[up[v]];
    ret = min(ret, d + min(q, w));
    p = par[up[v]];
    if (p == -1) break;
    d += depth[v] - depth[p];
    v = p;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  pre_dfs();
  dfs_hld();
  upv.init(n);
  downv.init(n);
  red(0);
  ;
  ;
  ;
  for (int _ = 0; _ < m; _++) {
    int t, v;
    cin >> t >> v;
    t--, v--;
    if (t == 0) {
      red(v);
    }
    if (t == 1) {
      cout << nearest(v) << '\n';
    }
  }
}
