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>
char _ibuf[(1 << 21 | 1)], _obuf[(1 << 21 | 1)], _stk[50];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + (1 << 21 | 1),
     *stkpos = _stk;
struct END {
  ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); }
} __;
inline int read() {
  register int x = 0, flag = 1;
  register char ch;
  while (!isdigit(
      ch = (ipos == iend and (iend = (ipos = _ibuf) +
                                     fread(_ibuf, 1, (1 << 21 | 1), stdin),
                              ipos == iend)
                ? EOF
                : *ipos++)))
    if (ch == '-') flag = -1;
  while (x = x * 10 + (ch & 15),
         isdigit(ch = (ipos == iend and
                               (iend = (ipos = _ibuf) +
                                       fread(_ibuf, 1, (1 << 21 | 1), stdin),
                                ipos == iend)
                           ? EOF
                           : *ipos++)))
    ;
  return x * flag;
}
template <typename _INT>
inline void write(_INT x) {
  if (x < 0)
    (opos == oend ? fwrite(_obuf, 1, (1 << 21 | 1), stdout), opos = _obuf : 0,
     *opos++ = ('-')),
        x = -x;
  while (*++stkpos = x % 10 ^ 48, x /= 10, x)
    ;
  while (stkpos != _stk)
    (opos == oend ? fwrite(_obuf, 1, (1 << 21 | 1), stdout), opos = _obuf : 0,
     *opos++ = (*stkpos--));
}
template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y) {
  return x < y ? x = y, true : false;
}
template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y) {
  return x > y ? x = y, true : false;
}
const int maxN = 1e5 + 5;
const int maxM = 1e5 + 5;
int n, m, len;
int dep[maxN], fa[maxN], top[maxN], son[maxN], size[maxN];
int mindis[maxN], dis[maxN];
int opt[maxM], node[maxM], id[maxM];
std::vector<int> G[maxN];
std::queue<int> q;
void DFS1(int u) {
  size[u] = 1;
  for (int v : G[u]) {
    if (fa[u] == v) continue;
    fa[v] = u, dep[v] = dep[u] + 1;
    DFS1(v);
    size[u] += size[v];
    if (size[son[u]] < size[v]) son[u] = v;
  }
}
void DFS2(int u) {
  if (son[u]) top[son[u]] = top[u], DFS2(son[u]);
  for (int v : G[u])
    if (!top[v]) top[v] = v, DFS2(v);
}
int Dis(int u, int v) {
  int res = dep[u] + dep[v];
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    u = fa[top[u]];
  }
  if (dep[u] > dep[v]) std::swap(u, v);
  return res - (dep[u] << 1);
}
int main() {
  n = read(), m = read();
  len = sqrt(n * log(n) / log(2));
  for (int i = 2; i <= n; ++i) {
    int u = read(), v = read();
    G[u].push_back(v), G[v].push_back(u);
  }
  DFS1(1), memcpy(mindis + 1, dep + 1, n * sizeof(int));
  top[1] = 1, DFS2(1);
  for (int i = 1; i <= m; ++i) opt[i] = read(), node[i] = read();
  id[0] = 1;
  for (int i = 1; i <= m; ++i) id[i] = (i - 1) / len + 1;
  for (int i = 1; i <= m; ++i) {
    if (id[i] != id[i - 1]) {
      memset(dis + 1, 0x3F, n * sizeof(int));
      for (int j = i - len; j < i; ++j)
        if (opt[j] == 1) q.push(node[j]), dis[node[j]] = 0;
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u])
          if (Chkmin(dis[v], dis[u] + 1)) q.push(v);
      }
      for (int i = 1; i <= n; ++i) Chkmin(mindis[i], dis[i]);
    }
    if (opt[i] == 2) {
      int ans = mindis[node[i]];
      for (int j = i - 1; j and id[j] == id[i]; --j)
        if (opt[j] == 1) Chkmin(ans, Dis(node[j], node[i]));
      write(ans), (opos == oend ? fwrite(_obuf, 1, (1 << 21 | 1), stdout),
                   opos = _obuf : 0, *opos++ = ('\n'));
    }
  }
  return 0;
}
