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;
struct edge {
  int nxt, t;
} e[100010 << 1];
int head[100010], edge_cnt;
void add_edge(int x, int y) {
  e[edge_cnt] = (edge){head[x], y};
  head[x] = edge_cnt++;
}
int A[100010];
struct Link_Cut_Tree {
  int son[100010][2], fa[100010], Lmn[100010], Rmn[100010], siz[100010];
  multiset<int> G[100010];
  void init(int x) {
    G[x].insert((0x3f3f3f3f));
    siz[x] = 1;
    Lmn[x] = Rmn[x] = (0x3f3f3f3f);
  }
  bool is_Rt(int x) { return son[fa[x]][0] != x && son[fa[x]][1] != x; }
  void Up(int now) {
    siz[now] = siz[son[now][0]] + siz[son[now][1]] + 1;
    int t = *G[now].begin();
    Lmn[now] =
        min(Lmn[son[now][0]], siz[son[now][0]] + 1 + min(t, Lmn[son[now][1]]));
    Rmn[now] =
        min(Rmn[son[now][1]], siz[son[now][1]] + 1 + min(t, Rmn[son[now][0]]));
  }
  void Rotate(int now) {
    int pre = fa[now];
    int P = fa[pre];
    int f = (son[pre][0] == now);
    bool Rt = is_Rt(pre);
    fa[now] = P;
    fa[pre] = now;
    fa[son[now][f]] = pre;
    if (!Rt) son[P][son[P][1] == pre] = now;
    son[pre][!f] = son[now][f];
    son[now][f] = pre;
    Up(pre);
  }
  void Splay(int now) {
    while (!is_Rt(now)) {
      int pre = fa[now];
      if (!is_Rt(pre)) {
        if ((son[fa[pre]][0] == pre) ^ (son[pre][0] == now)) {
          Rotate(now);
        } else {
          Rotate(pre);
        }
      }
      Rotate(now);
    }
    Up(now);
  }
  void Access(int now) {
    int Nxt = 0;
    for (; now > 0; Nxt = now, now = fa[now]) {
      Splay(now);
      if (son[now][1] > 0) {
        G[now].insert(Lmn[son[now][1]]);
      }
      son[now][1] = Nxt;
      if (son[now][1] > 0) {
        G[now].erase(G[now].find(Lmn[son[now][1]]));
      }
      Up(now);
    }
  }
  void Link(int x, int y) {
    if (y == 0) {
      return;
    }
    Access(y);
    Splay(y);
    Splay(x);
    fa[x] = y;
    G[y].insert(Lmn[x]);
    Up(y);
  }
  void Update(int x) {
    Access(x);
    Splay(x);
    G[x].erase(G[x].find((0x3f3f3f3f)));
    G[x].insert(0);
    A[x] = 1;
    Up(x);
  }
  int Query(int x) {
    Access(x);
    Splay(x);
    return Rmn[x] - 1;
  }
} LCT;
void dfs(int x, int f) {
  LCT.Link(x, f);
  int i;
  for (i = head[x]; ~i; i = e[i].nxt) {
    int to = e[i].t;
    if (to == f) {
      continue;
    }
    dfs(to, x);
  }
}
int main() {
  memset(head, -1, sizeof(head));
  int n, m, i;
  scanf("%d%d", &n, &m);
  for (i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add_edge(x, y);
    add_edge(y, x);
  }
  LCT.Lmn[0] = LCT.Rmn[0] = (0x3f3f3f3f);
  for (i = 1; i <= n; i++) {
    LCT.init(i);
  }
  dfs(1, 0);
  LCT.Update(1);
  for (i = 1; i <= m; i++) {
    int op, x;
    scanf("%d%d", &op, &x);
    if (op == 1) {
      LCT.Update(x);
    } else {
      printf("%d\n", LCT.Query(x));
    }
  }
  return 0;
}
