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;
queue<int> q;
int cs;
int n, m;
struct EDGE {
  int u, v, next;
} e[200000 + 10];
int cnt;
int head[100000 + 10];
int fa[100000 + 10][19];
int red[100 + 10];
int rnt;
int depth[100000 + 10];
int dis[100000 + 10];
int ans;
void adde(int u, int v) {
  e[++cnt].u = u;
  e[cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}
void readdata() {
  scanf("%d%d", &n, &m);
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    adde(u, v);
    adde(v, u);
  }
  e[0].next = 0;
}
void dfs(int u) {
  for (int i = head[u]; e[i].u == u; i = e[i].next) {
    if (depth[e[i].v] == 0) {
      depth[e[i].v] = depth[u] + 1;
      fa[e[i].v][0] = u;
      for (int j = 1; 1 << j <= depth[e[i].v]; j++)
        fa[e[i].v][j] = fa[fa[e[i].v][j - 1]][j - 1];
      dfs(e[i].v);
    }
  }
}
int go_up(int uu, int delta) {
  for (int i = 17; i >= 0; i--) {
    if (delta == 0) break;
    if ((1 << i) > delta) continue;
    delta -= 1 << i;
    uu = fa[uu][i];
  }
  return uu;
}
void lca(int uuu, int vvv) {
  int U = uuu;
  int V = vvv;
  int lc = 0;
  if (depth[uuu] != depth[vvv]) {
    lc += depth[uuu] - depth[vvv];
    U = go_up(uuu, depth[uuu] - depth[vvv]);
  }
  if (U == V) {
    ans = min(ans, lc);
    return;
  }
  for (int i = 17; i >= 0; i--) {
    if (fa[U][i] != fa[V][i]) {
      U = fa[U][i];
      V = fa[V][i];
      lc += (1 << i) * 2;
    }
  }
  lc += 2;
  ans = min(lc, ans);
}
void bfs() {
  while (!q.empty()) q.pop();
  for (int i = 1; i <= rnt; i++) {
    q.push(red[i]);
    dis[red[i]] = 0;
  }
  while (!q.empty()) {
    cs = q.front();
    q.pop();
    for (int i = head[cs]; e[i].u == cs; i = e[i].next) {
      int v = e[i].v;
      if (dis[v] > dis[cs] + 1) {
        dis[v] = dis[cs] + 1;
        q.push(v);
      }
    }
  }
}
int main() {
  readdata();
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  depth[1] = 1;
  red[++rnt] = 1;
  dfs(1);
  int uu;
  int bz;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &bz, &uu);
    if (bz == 1) {
      red[++rnt] = uu;
      if (rnt >= 100) {
        bfs();
        rnt = 0;
      }
      continue;
    }
    ans = dis[uu];
    for (int j = 1; j <= rnt; j++)
      if (depth[uu] > depth[red[j]])
        lca(uu, red[j]);
      else
        lca(red[j], uu);
    printf("%d\n", ans);
  }
}
