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 INF = 0x3f3f3f3f;
const long long LLINF = 1e18;
const int MAXN = 1e5;
int v, q;
vector<int> G[MAXN];
int min_dist[MAXN];
bool is_centroid[MAXN];
int sz[MAXN];
int father[MAXN];
int dfs_sz(int x, int f = -1) {
  sz[x] = 1;
  for (auto y : G[x]) {
    if (y == f || is_centroid[y]) continue;
    sz[x] += dfs_sz(y, x);
  }
  return sz[x];
}
int dfs_cd(int x, int cent_sz, int f = -1) {
  for (auto y : G[x]) {
    if (y == f || is_centroid[y]) continue;
    if (sz[y] > cent_sz / 2) return dfs_cd(y, cent_sz, x);
  }
  return x;
}
void cent_descomp(int x, int f = -1) {
  int cent_sz = dfs_sz(x);
  int centroid = dfs_cd(x, cent_sz);
  is_centroid[centroid] = true;
  father[centroid] = f;
  for (auto y : G[centroid]) {
    if (is_centroid[y]) continue;
    cent_descomp(y, centroid);
  }
}
int height[MAXN];
void dfs_h(int x, int f = -1) {
  for (auto y : G[x]) {
    if (f == y) continue;
    height[y] = height[x] + 1;
    dfs_h(y, x);
  }
}
int l;
int timer;
int tin[MAXN], tout[MAXN];
int up[MAXN][25];
void dfs(int v, int p) {
  tin[v] = ++timer;
  up[v][0] = p;
  for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
  for (int u : G[v]) {
    if (u != p) dfs(u, v);
  }
  tout[v] = ++timer;
}
bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (int i = l; i >= 0; --i) {
    if (!is_ancestor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}
void preprocess(int root) {
  timer = 0;
  l = ceil(log2(v));
  dfs(root, root);
}
int get_d(int x, int y) {
  return abs(height[x] + height[y] - 2 * height[lca(x, y)]);
}
void upd(int x) {
  int y = x;
  while (true) {
    min_dist[y] = min(min_dist[y], get_d(x, y));
    if (-1 == father[y]) break;
    y = father[y];
  }
}
int query(int x) {
  int y = x;
  int ans = INF;
  while (true) {
    ans = min(ans, min_dist[y] + get_d(x, y));
    if (-1 == father[y]) break;
    y = father[y];
  }
  return ans;
}
int main() {
  scanf("%d %d", &v, &q);
  for (int i = 1; i < v; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--, y--;
    G[x].push_back(y);
    G[y].push_back(x);
    min_dist[i - 1] = INF;
  }
  min_dist[v - 1] = INF;
  cent_descomp(0);
  for (int i = 0; i < v; i++) {
    if (father[i] == -1) {
      dfs_h(i);
      preprocess(i);
    }
  }
  upd(0);
  for (int _ = 0; _ < q; _++) {
    int t, x;
    scanf("%d %d", &t, &x);
    x--;
    if (t == 1)
      upd(x);
    else
      printf("%d\n", query(x));
  }
  return 0;
}
