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;
vector<int> adj[200010];
vector<int> cen[200010];
int ban[200010];
int sz[200010];
vector<int> h;
int height[200020];
pair<int, int> sp[22][200020];
pair<int, int> track[400020];
int anc[200020];
int ans[200020];
int n;
int bitcount(int m) {
  int z = -1;
  while (m) {
    m >>= 1;
    z++;
  }
  return z;
}
void dfs(int u, int p) {
  track[u].first = track[u].second = h.size();
  h.push_back(u);
  for (auto v : adj[u]) {
    if (v == p) continue;
    height[v] = height[u] + 1;
    dfs(v, u);
    h.push_back(u);
  }
  if (p == 0 || adj[u].size() > 1) {
    track[u].second = h.size() - 1;
  }
}
int lca(int a, int b) {
  if (track[a].first > track[b].first) swap(a, b);
  a = track[a].first;
  b = track[b].second;
  int c = b - a + 1;
  int z = bitcount(c), as;
  pair<int, int> u = sp[z][a];
  pair<int, int> v = sp[z][b - (1 << z) + 1];
  if (u.first > v.first)
    as = v.second;
  else
    as = u.second;
  return h[as];
}
void LCA() {
  int m, z, i, j;
  height[1] = 1;
  dfs(1, 0);
  m = h.size();
  z = -1;
  z = bitcount(m);
  for (i = 0; i < m; i++) {
    sp[0][i] = {height[h[i]], i};
  }
  for (i = 1; i < z + 1; i++) {
    for (j = 0; j < m - (1 << i) + 1; j++) {
      pair<int, int> u = sp[i - 1][j];
      pair<int, int> v = sp[i - 1][j + (1 << (i - 1))];
      if (u.first <= v.first)
        sp[i][j] = u;
      else
        sp[i][j] = v;
    }
  }
}
int dist(int u, int v) { return height[u] + height[v] - 2 * height[lca(u, v)]; }
void get_sz(int u, int p) {
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (ban[v] || v == p) continue;
    get_sz(v, u);
    sz[u] += sz[v];
  }
}
int centroid(int u, int p, int n) {
  for (auto v : adj[u]) {
    if (v == p || ban[v]) continue;
    if (sz[v] > n / 2) return centroid(v, u, n);
  }
  return u;
}
void start(int u, int p, int C) {
  get_sz(u, p);
  int c = centroid(u, p, sz[u]);
  ban[c] = 1;
  if (C != -1)
    anc[c] = C;
  else
    anc[c] = c;
  for (auto v : adj[c]) {
    if (!ban[v]) start(v, u, c);
  }
  ban[c] = 0;
}
void update(int x) {
  int u = x;
  while (anc[x] != x) {
    if (ans[x] == -1) ans[x] = 1e9 + 7;
    ans[x] = min(ans[x], dist(x, u));
    x = anc[x];
  }
  if (ans[x] == -1) ans[x] = 1e9 + 7;
  ans[x] = min(ans[x], dist(x, u));
}
int query(int x) {
  int u = x, mn = 1e9 + 7;
  while (anc[x] != x) {
    if (ans[x] == -1) ans[x] = 1e9 + 7;
    mn = min(mn, ans[x] + dist(x, u));
    x = anc[x];
  }
  if (ans[x] == -1) ans[x] = 1e9 + 7;
  mn = min(mn, ans[x] + dist(x, u));
  return mn;
}
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int i, j, k, a, b, c, x, y, z, q, m, t;
  memset(ans, -1, sizeof(ans));
  ;
  cin >> n >> q;
  for (i = 1; i < n; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  LCA();
  start(1, 0, -1);
  update(1);
  for (i = 0; i < q; i++) {
    cin >> t >> x;
    if (t == 1)
      update(x);
    else
      cout << query(x) << "\n";
  }
}
