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>
struct edge {
  int u, v;
} es[100000], qs[100000];
int n, q, cnt[100000], pos[2 * 100000], ans[100000], to[2 * 100000],
    par[100000][18], dep[100000], red[100000], dist[100000];
void dfs(int v, int pv) {
  int i, k;
  if (~pv) dep[v] = dep[pv] + 1;
  par[v][0] = pv;
  for (k = 0; ~par[v][k] && ~par[par[v][k]][k]; k++)
    par[v][k + 1] = par[par[v][k]][k];
  for (i = pos[v]; i < pos[v + 1]; i++)
    if (to[i] != pv) dfs(to[i], v);
}
int lca(int u, int v) {
  if (dep[u] > dep[v]) return lca(v, u);
  int dif = dep[v] - dep[u], i;
  for (i = 0; i < 18; i++)
    if (dif & (1 << i)) v = par[v][i];
  if (u == v) return u;
  for (i = 17; i >= 0; i--)
    if (par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  return par[u][0];
}
void bfs(int m) {
  int que[100000], l = 0, r = 0, v, i;
  memset(dist, -1, sizeof(dist));
  que[r++] = 0;
  dist[0] = 0;
  for (i = 0; i < m; i++)
    if (!qs[i].u) {
      que[r++] = qs[i].v;
      dist[qs[i].v] = 0;
    }
  while (l < r) {
    v = que[l++];
    for (i = pos[v]; i < pos[v + 1]; i++)
      if (dist[to[i]] < 0) {
        que[r++] = to[i];
        dist[to[i]] = dist[v] + 1;
      }
  }
}
void solve() {
  int i, b, j;
  for (i = 0; i < n; i++) pos[i + 1] = pos[i] + cnt[i];
  memset(cnt, 0, sizeof(cnt));
  for (i = 0; i < n - 1; i++) {
    int u = es[i].u, v = es[i].v;
    to[pos[u] + cnt[u]++] = v;
    to[pos[v] + cnt[v]++] = u;
  }
  memset(par, -1, sizeof(par));
  memset(ans, -1, sizeof(ans));
  red[0] = 1;
  dfs(0, -1);
  int m = 0, vs[317];
  for (b = 0; b < q; b += 317) {
    for (i = 0; i < m; i++) red[vs[i]] = 1;
    bfs(b);
    m = 0;
    for (i = b; i < ((b + 317) > (q) ? (q) : (b + 317)); i++) {
      if (!qs[i].u)
        vs[m++] = qs[i].v;
      else {
        ans[i] = dist[qs[i].v];
        for (j = 0; j < m; j++)
          ans[i] =
              ((ans[i]) > (dep[vs[j]] + dep[qs[i].v] -
                           2 * dep[lca(vs[j], qs[i].v)])
                   ? (dep[vs[j]] + dep[qs[i].v] - 2 * dep[lca(vs[j], qs[i].v)])
                   : (ans[i]));
      }
    }
  }
  for (i = 0; i < q; i++)
    if (~ans[i]) printf("%d\n", ans[i]);
}
void input() {
  scanf("%d %d", &n, &q);
  int u, v, i;
  for (i = 0; i < n - 1; i++) {
    scanf("%d %d", &u, &v);
    es[i].u = --u;
    es[i].v = --v;
    cnt[u]++;
    cnt[v]++;
  }
  for (i = 0; i < q; i++) {
    scanf("%d %d", &u, &v);
    qs[i].u = --u;
    qs[i].v = --v;
  }
}
int main() {
  input();
  solve();
  return 0;
}
