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 msize = 4e5 + 9;
const int oo = 1e9;
int head[msize], edge;
int to[msize], rmq[msize][33];
bool vis[msize];
int n, m;
queue<int> Q;
class Edge {
 public:
  int v, next;
} e[msize + msize];
void data() {
  memset(head, -1, sizeof(head));
  edge = 0;
}
void add(int u, int v) {
  e[edge].v = v;
  e[edge].next = head[u];
  head[u] = edge++;
}
int dep[msize], dfs_clock, e_c[msize], dis[msize];
void dfs(int u, int dd) {
  dep[u] = dd;
  to[dfs_clock] = u;
  e_c[u] = dfs_clock++;
  int v;
  for (int i = head[u]; ~i; i = e[i].next) {
    v = e[i].v;
    if (e_c[v] == -1) {
      dfs(v, dd + 1);
      to[dfs_clock++] = u;
    }
  }
}
int bit[msize];
void initRMQ() {
  bit[0] = -1;
  int n = dfs_clock;
  for (int i = 1; i <= n; ++i)
    bit[i] = (i & (i - 1)) == 0 ? bit[i - 1] + 1 : bit[i - 1];
  for (int i = 0; i <= n - 1; ++i) rmq[i][0] = dep[to[i]];
  for (int i = 1; i <= bit[n]; ++i)
    for (int j = 0; j + (1 << i) - 1 < n; ++j)
      rmq[j][i] = min(rmq[j][i - 1], rmq[j + (1 << i - 1)][i - 1]);
}
int RMQ(int l, int r) {
  l = e_c[l];
  r = e_c[r];
  if (l > r) swap(l, r);
  int t = bit[r - l + 1];
  r -= (1 << t) - 1;
  return min(rmq[l][t], rmq[r][t]);
}
void getclear() {
  dfs_clock = 0;
  memset(e_c, -1, sizeof(e_c));
  memset(dis, 0x3f, sizeof(dis));
}
void spfa() {
  memset(vis, 0, sizeof(vis));
  int u, v;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    vis[u] = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
      v = e[i].v;
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        if (!vis[v]) {
          Q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}
int getdis(int l, int r) {
  int lca = RMQ(l, r);
  return dep[l] + dep[r] - lca * 2;
}
int main() {
  int a, b;
  while (~scanf("%d%d", &n, &m)) {
    data();
    for (int i = 2; i <= n; ++i) {
      scanf("%d%d", &a, &b);
      add(a, b);
      add(b, a);
    }
    int block = sqrt(m);
    getclear();
    dfs(1, 0);
    initRMQ();
    Q.push(1);
    dis[1] = 0;
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &a, &b);
      if (a == 1) {
        Q.push(b);
        dis[b] = 0;
      } else if (a == 2) {
        int sz = Q.size();
        if (sz > block) {
          spfa();
          printf("%d\n", dis[b]);
        } else {
          int ans = dis[b];
          int bg = -1;
          while (!Q.empty()) {
            int q = Q.front();
            if (bg == -1)
              bg = q;
            else if (bg == q)
              break;
            Q.pop();
            ans = min(ans, getdis(b, q));
            Q.push(q);
          }
          printf("%d\n", ans);
        }
      }
    }
  }
  return 0;
}
