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;
bool markcentroid[100005];
int subtree[100005], glob_d, par[100005][20], cntr_par[100005], dis[100005],
    ans[100005];
vector<int> v[100005], cntrtree[100005];
int cntnode(int n, int p) {
  subtree[n] = 1;
  for (int i = 0; i < v[n].size(); i++) {
    if (v[n][i] != p && !markcentroid[v[n][i]])
      subtree[n] += cntnode(v[n][i], n);
  }
  return subtree[n];
}
int dfs(int n, int p, int tot) {
  glob_d++;
  for (int i = 0; i < v[n].size(); i++) {
    if (v[n][i] != p && !markcentroid[v[n][i]]) {
      if (subtree[v[n][i]] > tot / 2) {
        return dfs(v[n][i], n, tot);
      }
    }
  }
  return n;
}
int centroid(int root, int p) {
  int a;
  int tot = cntnode(root, p);
  glob_d = 0;
  int cntr = dfs(root, p, tot);
  cntr_par[cntr] = p;
  markcentroid[cntr] = 1;
  for (int i = 0; i < v[cntr].size(); i++) {
    if (markcentroid[v[cntr][i]]) continue;
    a = centroid(v[cntr][i], cntr);
    cntrtree[a].push_back(cntr);
    cntrtree[cntr].push_back(a);
  }
  return cntr;
}
int findpar(int n, int p) {
  for (int i = 0; p > 0; i++) {
    if ((p & (1 << i)) != 0) {
      n = par[n][i];
      p -= (1 << i);
    }
  }
  return n;
}
void getdis(int n, int p, int d) {
  par[n][0] = p;
  dis[n] = d++;
  for (int i = 0; i < v[n].size(); i++) {
    if (v[n][i] != p) getdis(v[n][i], n, d);
  }
}
void visit(int n, int p) {
  printf("%d: start\n", n);
  for (int i = 0; i < cntrtree[n].size(); i++) {
    if (cntrtree[n][i] != p) visit(cntrtree[n][i], n);
  }
  printf("%d: end\n", n);
}
int lca(int a, int b) {
  if (dis[a] > dis[b]) swap(a, b);
  b = findpar(b, dis[b] - dis[a]);
  for (int i = 19; i >= 0 && a != b; i--) {
    if (par[a][i] != par[b][i]) {
      b = par[b][i];
      a = par[a][i];
    }
  }
  if (a != b) a = par[a][0];
  return a;
}
int finddis(int a, int b) { return dis[a] + dis[b] - 2 * dis[lca(a, b)]; }
int query(int n) {
  int u = n;
  int tmp = 1000000000;
  while (u > 0) {
    tmp = min(finddis(n, u) + ans[u], tmp);
    u = cntr_par[u];
  }
  return tmp;
}
void update(int n) {
  int u = n;
  while (n > 0) {
    ans[n] = min(ans[n], finddis(n, u));
    n = cntr_par[n];
  }
}
int main() {
  int n, a, b, i, tmp, q;
  scanf("%d %d", &n, &q);
  for (i = 1; i < n; i++) {
    scanf("%d %d", &a, &b);
    v[b].push_back(a);
    v[a].push_back(b);
  }
  getdis(1, 0, 0);
  for (i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      par[j][i] = par[par[j][i - 1]][i - 1];
    }
  }
  a = centroid(1, 0);
  for (i = 1; i <= n; i++) ans[i] = 1000000000;
  update(1);
  while (q--) {
    scanf("%d %d", &a, &b);
    if (a == 1) {
      update(b);
    } else if (a == 2) {
      tmp = query(b);
      if (tmp == 1000000000) tmp = -1;
      printf("%d\n", tmp);
    } else {
      scanf("%d", &a);
      printf("%d\n", finddis(a, b));
    }
  }
  return 0;
}
