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 ull = unsigned long long;
using ll = long long;
const int N = 100005, LG = 18, B_SZ = 400;
int n, m;
vector<int> g[N];
int cl[N], vr[N], dst[N];
void bfs() {
  queue<int> q;
  for (int i = 1; i <= n; ++i) {
    dst[i] = (int)2e9;
    if (cl[i]) {
      dst[i] = 0;
      q.push(i);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (dst[v] > dst[u] + 1) {
        dst[v] = dst[u] + 1;
        q.push(v);
      }
    }
  }
}
int dep[N], jmp[LG + 1][N];
void dfs(int u, int p = -1) {
  for (auto v : g[u]) {
    if (v != p) {
      dep[v] = dep[u] + 1;
      jmp[0][v] = u;
      dfs(v, u);
    }
  }
}
int lca(int u, int v) {
  if (dep[v] > dep[u]) swap(u, v);
  for (int i = LG; i >= 0; --i) {
    if (dep[u] - (1 << i) >= dep[v]) {
      u = jmp[i][u];
    }
  }
  if (u == v) return u;
  for (int j = LG; j >= 0; --j) {
    if (jmp[j][u] != jmp[j][v]) {
      u = jmp[j][u], v = jmp[j][v];
    }
  }
  return jmp[0][u];
}
int dist(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }
void lca_init() {
  dfs(1);
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      jmp[j][i] = jmp[j - 1][jmp[j - 1][i]];
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 0, u, v; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].push_back(v), g[v].push_back(u);
  }
  cl[1] = 1, bfs();
  lca_init();
  int sc = B_SZ;
  vector<int> vt;
  for (int i = 0, t, v; i < m; ++i) {
    if (sc-- == 0) {
      bfs();
      vt.clear();
      sc = B_SZ;
    }
    cin >> t >> v;
    if (t == 1) {
      cl[v] = 1;
      vt.push_back(v);
    } else {
      int x = dst[v];
      for (auto p : vt) {
        x = min(x, dist(v, p));
      }
      cout << x << '\n';
    }
  }
  return 0;
}
