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 long long Mxn = 2e5 + 7;
const long long Mod = 1e9 + 7;
const long long Inf = 1e14 + 7;
void Kultivator() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int d[Mxn][20], lvl[Mxn], Parent[Mxn], n, M;
vector<int> g[Mxn], H[Mxn], Best(Mxn, Mod);
int Cn, Cnt[Mxn];
bool Used[Mxn], Qw;
int Ans;
void dfs(int x, int p) {
  lvl[x] = lvl[p] + 1;
  d[x][0] = p;
  for (int i = 1; i <= 18; i++) {
    d[x][i] = d[d[x][i - 1]][i - 1];
  }
  for (auto to : g[x]) {
    if (to != p) dfs(to, x);
  }
}
int lca(int u, int v) {
  if (lvl[u] < lvl[v]) {
    swap(u, v);
  }
  int dif = lvl[u] - lvl[v];
  for (int j = 0; j <= 18; j++) {
    if ((1 << j) & dif) {
      u = d[u][j];
    }
  }
  if (u == v) return u;
  for (int i = 18; i >= 0; i--) {
    if (d[u][i] != d[v][i]) {
      u = d[u][i];
      v = d[v][i];
    }
  }
  return d[u][0];
}
int Calc(int v, int p) {
  Cnt[v] = true;
  for (int to : g[v]) {
    if (to == p || Used[to]) continue;
    Cnt[v] += Calc(to, v);
  }
  return Cnt[v];
}
int Find(int v, int p) {
  for (int to : g[v]) {
    if (to == p || Used[to] || Cnt[to] <= (Cn / 2)) continue;
    return Find(to, v);
  }
  return v;
}
int Build(int v, int p = -1) {
  Cn = Calc(v, v);
  int Centroid = Find(v, v);
  Used[Centroid] = true;
  Parent[Centroid] = p;
  for (int to : g[Centroid]) {
    if (Used[to]) continue;
    Build(to, Centroid);
  }
  return Centroid;
}
void change(int v, int p) {
  if (p == -1) return;
  Best[p] = min(Best[p], lvl[v] + lvl[p] - 2 * lvl[lca(v, p)]);
  change(v, Parent[p]);
}
void Upd(int v, int p) {
  if (p == -1) return;
  Ans = min(Ans, Best[p] + lvl[v] + lvl[p] - 2 * lvl[lca(v, p)]);
  Upd(v, Parent[p]);
}
int main() {
  Kultivator();
  cin >> n >> M;
  for (int i = 1, L, R; i < n; i++) {
    cin >> L >> R;
    g[L].push_back(R);
    g[R].push_back(L);
  }
  dfs(1, 0);
  Build(1);
  change(1, 1);
  while (M--) {
    int Type, w;
    cin >> Type >> w;
    if (Type == 1)
      change(w, w);
    else {
      Ans = Mod;
      Upd(w, w);
      cout << Ans << '\n';
    }
  }
}
