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 = 1000005;
int ne[N << 1], Log2[N << 1], tot, fi[N], zz[N << 1], sd[N], st[21][N << 1],
    a[N << 1], opt, x, y, n, q, fa[N];
int size[N], f[N], flag[N], in[N], out[N], Min[N], fa2[N];
vector<int> g;
void jb(int x, int y) {
  ne[++tot] = fi[x];
  fi[x] = tot;
  zz[tot] = y;
}
int cmp(int x, int y) { return sd[x] < sd[y] ? x : y; }
int pd(int x, int y) {
  if (!x) return 1;
  return in[x] <= in[y] && out[x] >= out[y];
}
int find(int l, int r) {
  int k = Log2[r - l + 1];
  return cmp(st[k][l], st[k][r - (1 << k) + 1]);
}
int lca(int x, int y) {
  if (in[x] > in[y]) swap(x, y);
  if (pd(x, y)) return x;
  return fa2[find(out[x], in[y])];
}
int dis(int x, int y) { return sd[x] + sd[y] - 2 * sd[lca(x, y)]; }
void dfs(int x, int y, int z) {
  sd[x] = z;
  in[x] = ++tot;
  a[tot] = x;
  fa2[x] = y;
  for (int i = fi[x]; i; i = ne[i])
    if (zz[i] != y) dfs(zz[i], x, z + 1);
  out[x] = ++tot;
  a[tot] = x;
}
void dfs2(int x, int y) {
  f[x] = y;
  g.push_back(x);
  size[x] = 1;
  for (int i = fi[x]; i; i = ne[i])
    if (!flag[zz[i]] && zz[i] != y) dfs2(zz[i], x), size[x] += size[zz[i]];
}
int findroot(int x) {
  g.clear();
  dfs2(x, 0);
  for (int i : g) {
    int Flag = 1, cnt = g.size() - 1;
    for (int j = fi[i]; j; j = ne[j])
      if (!flag[zz[j]] && zz[j] != f[i]) {
        if (size[zz[j]] > (int)g.size() / 2) Flag = 0;
        cnt -= size[zz[j]];
      }
    if (cnt > (int)g.size() / 2) Flag = 0;
    if (Flag) return i;
  }
  return -1;
}
void solve(int x, int y) {
  x = findroot(x);
  flag[x] = 1;
  fa[x] = y;
  for (int i = fi[x]; i; i = ne[i])
    if (!flag[zz[i]]) solve(zz[i], x);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    jb(x, y);
    jb(y, x);
  }
  tot = 0;
  dfs(1, 0, 1);
  for (int i = 1; i <= n * 2; i++) st[0][i] = a[i];
  for (int i = 1; i <= n * 2; i++) Log2[i] = log2(i);
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j <= n * 2 - (1 << i) + 1; j++)
      st[i][j] = cmp(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  solve(1, 0);
  for (int i = 1; i <= n; i++) Min[i] = 1e9;
  y = 1;
  while (y) Min[y] = min(Min[y], dis(1, y)), y = fa[y];
  while (q--) {
    scanf("%d%d", &opt, &x);
    int y = x;
    if (opt == 1) {
      while (y) {
        Min[y] = min(Min[y], dis(x, y));
        y = fa[y];
      }
    } else {
      int ans = 1e9;
      while (y) {
        ans = min(ans, dis(x, y) + Min[y]);
        y = fa[y];
      }
      if (ans == 1e9)
        puts("-1");
      else
        printf("%d\n", ans);
    }
  }
  return 0;
}
