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 N = 1e5 + 10;
const int level = 20;
vector<int> adj[N];
bool checked[N];
int parent[N];
int sz[N];
int centroid;
int sparse[N][level];
int depth[N];
void subtree(int cur, int prev) {
  sz[cur] = 1;
  for (auto &child : adj[cur]) {
    if (child != prev and !checked[child]) {
      subtree(child, cur);
      sz[cur] += sz[child];
    }
  }
}
void decompose(int cur, int prev, int total_size) {
  for (auto &child : adj[cur]) {
    if (child != prev and !checked[child]) {
      decompose(child, cur, total_size);
    }
  }
  if (centroid != -1) {
    return;
  }
  if (2 * sz[cur] >= total_size) {
    centroid = cur;
    return;
  }
}
int get_centroid(int cur) {
  subtree(cur, 0);
  centroid = -1;
  decompose(cur, 0, sz[cur]);
  return centroid;
}
void dfs(int cur, int prev) {
  int root = get_centroid(cur);
  parent[root] = prev;
  checked[root] = true;
  for (auto &child : adj[root]) {
    if (!checked[child]) {
      dfs(child, root);
    }
  }
}
void dfs_sparse(int cur, int prev) {
  sparse[cur][0] = prev;
  for (auto &child : adj[cur]) {
    if (child != prev) {
      depth[child] = depth[cur] + 1;
      dfs_sparse(child, cur);
    }
  }
}
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(1, 0);
  dfs_sparse(1, -1);
  for (int l = 1; l < level; l++) {
    for (int node = 1; node <= n; node++) {
      if (sparse[node][l - 1] != -1) {
        sparse[node][l] = sparse[sparse[node][l - 1]][l - 1];
      }
    }
  }
  auto lca = [&](int u, int v) -> int {
    if (depth[v] < depth[u]) {
      swap(u, v);
    }
    int diff = depth[v] - depth[u];
    for (int i = 0; i < level; i++) {
      if ((diff >> i) & 1) {
        v = sparse[v][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int i = level - 1; i >= 0; i--) {
      if (sparse[u][i] != sparse[v][i]) {
        u = sparse[u][i];
        v = sparse[v][i];
      }
    }
    return sparse[u][0];
  };
  auto get_dist = [&](int x, int y) {
    int lc = lca(x, y);
    return depth[x] + depth[y] - 2 * depth[lc];
  };
  vector<int> dist(n + 1, n);
  int node = 1;
  for (int i = node; i; i = parent[i]) {
    dist[i] = get_dist(i, node);
  }
  for (int i = 1; i <= m; i++) {
    int type, node;
    cin >> type >> node;
    if (type == 1) {
      for (int i = node; i; i = parent[i]) {
        dist[i] = min(dist[i], get_dist(i, node));
      }
    } else {
      int ans = n;
      for (int i = node; i; i = parent[i]) {
        ans = min(ans, get_dist(i, node) + dist[i]);
      }
      cout << (dist[node] = ans) << '\n';
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}
