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 maxn = 1e5;
vector<int> red;
int head[maxn + 5], father[maxn + 5][20], dep[maxn + 5], dep1[maxn + 5];
int mn;
int lg[maxn + 5];
int n, m, x, y;
int op[maxn + 5], v[maxn + 5];
int L[5000], R[5000];
bool vis[maxn + 5];
int dis[maxn + 5];
int ans[maxn + 5];
queue<int> q;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + ch - '0';
  return x * f;
}
struct edge {
  int to, _next;
} G[2 * maxn + 5];
int num = 0;
void add(int u, int v) {
  G[++num].to = v;
  G[num]._next = head[u];
  head[u] = num;
}
void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  father[u][0] = fa;
  for (int i = 1; (1 << i) <= dep[u]; i++)
    father[u][i] = father[father[u][i - 1]][i - 1];
  for (int i = head[u]; i; i = G[i]._next) {
    int v = G[i].to;
    if (v == fa) continue;
    dfs(v, u);
  }
}
int LCA(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  while (dep[x] > dep[y]) x = father[x][lg[dep[x] - dep[y]]];
  if (x == y) return x;
  for (int k = lg[dep[x]]; k >= 0; k--)
    if (father[x][k] != father[y][k]) {
      x = father[x][k];
      y = father[y][k];
    }
  return father[x][0];
}
int dist(int x, int y) {
  int t = LCA(x, y);
  return dep[x] + dep[y] - 2 * dep[t];
}
void setLg(int n) {
  lg[0] = -1;
  for (int i = 1; i <= n; i++)
    if (i & (i - 1))
      lg[i] = lg[i - 1];
    else
      lg[i] = lg[i - 1] + 1;
}
void bfs() {
  memset(vis, false, sizeof(vis));
  while (q.size()) q.pop();
  for (int i = 0; i < red.size(); i++) {
    q.push(red[i]);
    vis[red[i]] = true;
    dis[red[i]] = 0;
  }
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = G[i]._next) {
      int v = G[i].to;
      if (!vis[v]) {
        q.push(v);
        vis[v] = true;
        dis[v] = dis[u] + 1;
      }
    }
  }
}
int main() {
  setLg(maxn);
  n = read();
  m = read();
  for (int i = 0; i < n - 1; i++) {
    x = read();
    y = read();
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  int sz = pow(2.5 * m * log(n) / log(2.0), 1.0 / 3) + 1;
  int k = m / sz;
  for (int i = 1; i <= m; i++) op[i] = read(), v[i] = read();
  for (int i = 1; i <= k; i++) L[i] = (i - 1) * sz + 1, R[i] = i * sz;
  if (k * sz < m) {
    L[k + 1] = k * sz + 1;
    R[k + 1] = m;
    k++;
  }
  red.push_back(1);
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= k; i++) {
    bfs();
    for (int l = L[i]; l <= R[i]; l++)
      if (op[l] == 2) ans[l] = dis[v[l]];
    for (int l = L[i]; l <= R[i]; l++)
      if (op[l] == 1)
        for (int r = l + 1; r <= R[i]; r++)
          if (op[r] == 2) ans[r] = min(ans[r], dist(v[r], v[l]));
    for (int l = L[i]; l <= R[i]; l++)
      if (op[l] == 1) red.push_back(v[l]);
  }
  for (int i = 1; i <= m; i++)
    if (op[i] == 2) printf("%d\n", ans[i]);
  return 0;
}
