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 int N = 100010;
int n, m, m1, red[N], q[N], f[N], lv[N], p[2 * N][20], E[2 * N], pos[N];
vector<int> ke[N];
void enter() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i < n; ++i) {
    scanf("%d%d", &u, &v);
    ke[u].push_back(v);
    ke[v].push_back(u);
  }
}
void build_tree(int u, int c) {
  E[0]++;
  E[E[0]] = u;
  p[E[0]][0] = u;
  pos[u] = E[0];
  for (vector<int>::iterator i = ke[u].begin(); i != ke[u].end(); ++i)
    if (*i != c) lv[*i] = lv[u] + 1, build_tree(*i, u);
  if (c != 0) E[0]++;
  E[E[0]] = c;
  p[E[0]][0] = c;
}
void pre_LCA() {
  for (int j = 1; (1 << j) <= E[0]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= E[0]; ++i)
      p[i][j] = (lv[p[i][j - 1]] < lv[p[i + (1 << (j - 1))][j - 1]])
                    ? p[i][j - 1]
                    : p[i + (1 << (j - 1))][j - 1];
}
int LCA(int u, int v) {
  if (pos[u] > pos[v]) swap(u, v);
  u = pos[u];
  v = pos[v];
  int k = log2(v - u + 1);
  return lv[p[u][k]] < lv[p[v - (1 << k) + 1][k]] ? p[u][k]
                                                  : p[v - (1 << k) + 1][k];
}
void process() {
  build_tree(1, 0);
  pre_LCA();
  for (int i = 1; i <= n; ++i) f[i] = 1e9;
  int u, m1 = sqrt(m), _ = 0, l = 1, r = 1, c, ans;
  red[1] = 1;
  q[1] = 1;
  f[1] = 0;
  while (_ < m) {
    while (l <= r) {
      u = q[l];
      l++;
      for (vector<int>::iterator i = ke[u].begin(); i != ke[u].end(); ++i)
        if (f[u] + 1 < f[*i]) f[*i] = f[u] + 1, r++, q[r] = *i;
    }
    l = 1, r = 0;
    for (int i = 1; i <= min(m - _, m1); ++i) {
      scanf("%d%d", &c, &u);
      if (c == 1)
        red[u] = 1, f[u] = 0, r++, q[r] = u;
      else {
        ans = f[u];
        for (int i = l; i <= r; ++i) {
          c = LCA(u, q[i]);
          ans = min(ans, lv[u] + lv[q[i]] - 2 * lv[c]);
        }
        printf("%d\n", ans);
      }
    }
    _ += min(m - _, m1);
  }
}
int main() {
  enter();
  process();
  return 0;
}
