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 MAXK = 17;
const int MAXN = 1 << MAXK;
vector<int> G[MAXN];
int up[MAXN][MAXK + 1];
int depth[MAXN];
void dfs(int v, int p, int d) {
  up[v][0] = p;
  depth[v] = d;
  for (int u : G[v]) {
    if (u != p) dfs(u, v, d + 1);
  }
}
int la(int v, int level) {
  int k = MAXK;
  int pow = 1 << MAXK;
  while (k >= 0) {
    if (level >= pow) {
      v = up[v][k];
      level -= pow;
    }
    pow /= 2;
    --k;
  }
  return v;
}
int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  u = la(u, depth[u] - depth[v]);
  if (u == v) return u;
  int k = MAXK;
  while (k >= 0) {
    if (up[u][k] != up[v][k]) {
      u = up[u][k];
      v = up[v][k];
    }
    --k;
  }
  return up[u][0];
}
int dist[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    G[a - 1].emplace_back(b - 1);
    G[b - 1].emplace_back(a - 1);
  }
  dfs(0, 0, 0);
  for (int j = 1; j <= MAXK; ++j) {
    for (int i = 0; i < n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
  }
  for (int i = 0; i < n; ++i) dist[i] = depth[i];
  vector<int> red;
  red.emplace_back(0);
  vector<int> stack;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --b;
    if (a == 1) {
      stack.emplace_back(b);
      red.emplace_back(b);
      if (stack.size() >= 77) {
        fill(dist, dist + n, n);
        deque<int> Q;
        for (int x : red) {
          dist[x] = 0;
          Q.emplace_back(x);
        }
        while (!Q.empty()) {
          int v = Q.front();
          Q.pop_front();
          for (int u : G[v]) {
            if (dist[u] == n) {
              dist[u] = dist[v] + 1;
              Q.emplace_back(u);
            }
          }
        }
        vector<int>().swap(stack);
      }
    } else {
      int ans = dist[b];
      for (int x : stack)
        ans = min(ans, depth[b] + depth[x] - 2 * depth[lca(b, x)]);
      cout << ans << '\n';
    }
  }
  return 0;
}
