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 maxn = 200010;
const int INF = 1 << 29;
int N, tn, n, m, tot;
int fs[maxn], nxt[maxn * 2], oth[maxn * 2];
int q[maxn], fa[maxn], dis[maxn], son[maxn], size[maxn];
int lit[maxn], jump[maxn], sl[maxn];
int fir[maxn], pos[maxn], bel[maxn];
int D0[maxn * 4], D1[maxn * 4];
bool col[maxn];
multiset<pair<int, int> > S;
inline int gm(int *a, int k, int l, int r, int x, int y) {
  if (l == x && r == y) return a[k];
  int mid = (l + r) >> 1;
  if (y <= mid) return gm(a, ((k) << 1), l, mid, x, y);
  if (x > mid) return gm(a, (((k) << 1) + 1), mid + 1, r, x, y);
  return min(gm(a, ((k) << 1), l, mid, x, mid),
             gm(a, (((k) << 1) + 1), mid + 1, r, mid + 1, y));
}
int M = 0;
void init() {
  int i, x, y, head, tail, u, t, p, j;
  scanf("%d%d", &N, &M);
  for (i = 1; i < N; ++i) {
    scanf("%d%d", &x, &y);
    oth[++m] = y, nxt[m] = fs[x], fs[x] = m;
    oth[++m] = x, nxt[m] = fs[y], fs[y] = m;
  }
  for (q[head = tail = 1] = 1; head <= tail;)
    for (i = fs[u = q[head++]]; i; i = nxt[i])
      if (oth[i] != fa[u]) fa[q[++tail] = oth[i]] = u;
  for (j = N; j; --j)
    for (u = q[j], size[u] = 1, i = fs[u]; i; i = nxt[i])
      if ((t = oth[i]) != fa[u]) {
        size[u] += size[t];
        if (size[son[u]] < size[t]) son[u] = t;
      }
  for (j = 2; j <= N; ++j)
    u = q[j], lit[u] = lit[fa[u]] + (son[fa[u]] != u), dis[u] = dis[fa[u]] + 1;
  for (j = 1; j <= N; ++j)
    if (!son[j]) {
      for (p = j;; p = fa[p])
        if (son[fa[p]] != p) break;
      for (sl[++n] = tot + 1, i = fir[n] = p; i; i = son[i])
        bel[i] = n, jump[i] = fa[fir[n]], pos[i] = ++tot;
    }
  sl[n + 1] = N + 1;
  for (tn = 1; tn < N; tn <<= 1)
    ;
  for (i = tn; i < N + tn; ++i) D0[i] = INF - i, D1[i] = INF + i;
  for (i = tn - 1; i; --i)
    D0[i] = min(D0[((i) << 1)], D0[(((i) << 1) + 1)]),
    D1[i] = min(D1[((i) << 1)], D1[(((i) << 1) + 1)]);
  for (i = 1; i <= n; ++i)
    if (jump[fir[i]])
      S.insert(make_pair(
          (jump[p]),
          (gm((D1), 1, 1, tn, (sl[i]), (sl[i + 1] - 1)) - sl[i] + 1)));
}
void change(int x) {
  int t;
  multiset<pair<int, int> >::iterator it;
  if (col[x])
    S.erase(S.find(make_pair((x), (0))));
  else
    S.insert(make_pair((x), (0)));
  for (col[x] ^= 1; x; x = jump[x]) {
    n = bel[x];
    if (jump[x] && !S.empty()) {
      it = S.find(make_pair(
          (jump[x]),
          (gm((D1), 1, 1, tn, (sl[n]), (sl[n + 1] - 1)) - sl[n] + 1)));
      if (it != S.end()) S.erase(it);
    }
    if (!S.empty()) {
      it = S.lower_bound(make_pair((x), (-INF)));
      t = (it != S.end() && it->first == x) ? it->second : INF;
    } else
      t = INF;
    D0[pos[x] + tn - 1] = t - pos[x], D1[pos[x] + tn - 1] = t + pos[x];
    for (t = (pos[x] + tn - 1) >> 1; t; t >>= 1)
      D0[t] = min(D0[((t) << 1)], D0[(((t) << 1) + 1)]),
      D1[t] = min(D1[((t) << 1)], D1[(((t) << 1) + 1)]);
    if (jump[x])
      S.insert(make_pair(
          (jump[x]),
          (gm((D1), 1, 1, tn, (sl[n]), (sl[n + 1] - 1)) - sl[n] + 1)));
  }
}
int query(int x) {
  if (col[x]) return 0;
  int ans = INF, s = 0, t, n;
  for (; x; s += dis[x] - dis[jump[x]], x = jump[x]) {
    if (s >= ans) break;
    n = bel[x];
    t = min(gm((D0), 1, 1, tn, (sl[n]), (pos[x])) + pos[x],
            gm((D1), 1, 1, tn, (pos[x]), (sl[n + 1] - 1)) - pos[x]);
    ans = min(ans, t + s);
  }
  return ans >= N ? -1 : ans;
}
int main() {
  int opt, x;
  init();
  change(1);
  while (M--) {
    scanf("%d%d", &opt, &x);
    if (opt == 2)
      printf("%d\n", query(x));
    else
      change(x);
  }
  return 0;
}
