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 = 2e5;
const int inf = 1e8;
vector<int> v[N];
queue<int> p;
bool ax[N];
int q, n, az;
int stk[N], top;
int dist[N], ans[N];
int f[N][20], dep[N];
void dfs(int fath, int x) {
  dep[x] = dep[fath] + 1;
  ans[x] = dep[x] - 1;
  f[x][0] = fath;
  for (int i = 0; i < v[x].size(); i++) {
    int dot = v[x][i];
    if (dot == fath) continue;
    dfs(x, dot);
  }
}
int lca(int x, int y) {
  if (dep[y] > dep[x]) swap(x, y);
  for (int i = 17; i >= 0; i--) {
    if (dep[f[x][i]] >= dep[y]) x = f[x][i];
  }
  if (x == y) return x;
  for (int i = 17; i >= 0; i--)
    if (f[y][i] != f[x][i]) {
      y = f[y][i];
      x = f[x][i];
    }
  return f[y][0];
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs(0, 1);
  for (int i = 1; i <= 17; i++)
    for (int j = 1; j <= n; j++) f[j][i] = f[f[j][i - 1]][i - 1];
  az = sqrt(q);
  az++;
  for (int i = 1; i <= q; i++) {
    int op, dot;
    cin >> op >> dot;
    if (op == 1) {
      top++;
      stk[top] = dot;
      if (top >= az) {
        for (int i = 1; i <= n; i++) dist[i] = inf;
        dist[1] = 0;
        p.push(1);
        for (int i = 1; i <= top; i++) {
          dist[stk[i]] = 0;
          p.push(stk[i]);
          stk[i] = 0;
        }
        while (p.empty() != 1) {
          int zl = p.front();
          p.pop();
          for (int i = 0; i < v[zl].size(); i++) {
            int dot = v[zl][i];
            if (dist[dot] == inf) {
              dist[dot] = dist[zl] + 1;
              p.push(dot);
            }
          }
        }
        for (int i = 1; i <= n; i++) ans[i] = min(ans[i], dist[i]);
        top = 0;
      }
    } else {
      for (int i = 1; i <= top; i++) {
        int cal = dep[stk[i]] + dep[dot] - 2 * dep[lca(dot, stk[i])];
        ans[dot] = min(ans[dot], cal);
      }
      cout << ans[dot] << endl;
    }
  }
  return 0;
}
