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>
#pragma G++ optimize(2)
using namespace std;
template <typename T>
inline void read(T &FF) {
  int RR = 1;
  FF = 0;
  char CH = getchar();
  for (; !isdigit(CH); CH = getchar())
    if (CH == '-') RR = -RR;
  for (; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
  FF *= RR;
}
inline void file(string str) {
  freopen((str + ".in").c_str(), "r", stdin);
  freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10, Log = 21;
int n, q, now, fst[N], nxt[N << 1], num[N << 1];
int fa[N][Log + 1], dep[N], st[N + 1];
void add(int u, int v) {
  nxt[++now] = fst[u], fst[u] = now, num[now] = v;
  nxt[++now] = fst[v], fst[v] = now, num[now] = u;
}
void get_fa(int x) {
  dep[x] = dep[fa[x][0]] + 1;
  for (int i = 1; i <= Log; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
  for (int i = fst[x]; i; i = nxt[i]) {
    if (num[i] != fa[x][0]) fa[num[i]][0] = x, get_fa(num[i]);
  }
}
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = Log; i >= 0; i--)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = Log; i >= 0; i--)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[get_lca(x, y)]; }
vector<int> op;
void bfs() {
  queue<int> qi;
  for (auto i : op) qi.push(i), st[i] = 0;
  op.clear();
  while (!qi.empty()) {
    int pi = qi.front();
    qi.pop();
    for (int i = fst[pi]; i; i = nxt[i])
      if (st[pi] + 1 < st[num[i]]) st[num[i]] = st[pi] + 1, qi.push(num[i]);
  }
}
int main() {
  read(n), read(q);
  int u = 0, v = 0;
  for (int i = 1; i < n; i++) read(u), read(v), add(u, v);
  memset(st, 0x3f, sizeof(st));
  get_fa(1);
  op.push_back(1);
  bfs();
  int opx, opy, s = sqrt(q);
  for (int i = 1; i <= q; i++) {
    read(opx), read(opy);
    if (opx == 1)
      op.push_back(opy);
    else {
      int res = st[opy];
      for (auto j : op) res = min(res, dist(j, opy));
      printf("%d\n", res);
    }
    if (i % s == 0) bfs();
  }
  return 0;
}
