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 MAGIC = 300;
const int N = 1e5 + 100;
const int INF = 1e9;
int n, m;
vector<int> tree[N], list_good;
int is_good[N], red[N];
int ans_good[400][N];
pair<int, int> q[N];
int dfs(int v, int par) {
  int sz = 0;
  for (auto i : tree[v]) {
    if (i != par) {
      sz += dfs(i, v);
    }
  }
  sz++;
  if (sz > MAGIC) {
    is_good[v] = list_good.size();
    list_good.push_back(v);
    sz = 0;
  }
  return sz;
}
int get_ans(int v, int par, int depth, int i) {
  if (is_good[v] != -1) {
    return depth + ans_good[is_good[v]][i];
  } else if (red[v] < i) {
    return depth;
  } else {
    int mn = INF;
    for (auto j : tree[v]) {
      if (j != par) {
        mn = min(mn, get_ans(j, v, depth + 1, i));
      }
    }
    return mn;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    is_good[i] = -1;
    red[i] = INF;
  }
  red[1] = 0;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  dfs(1, 0);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &q[i].first, &q[i].second);
    if (q[i].first == 1) {
      red[q[i].second] = i;
    }
  }
  for (int i = 0; i < (int)list_good.size(); i++) {
    int good = list_good[i];
    for (int j = 0; j <= m; j++) {
      ans_good[i][j] = INF;
    }
    queue<int> bfs;
    vector<int> dist(n + 1, 0);
    bfs.push(good);
    dist[good] = 1;
    while (bfs.size()) {
      int cur = bfs.front();
      bfs.pop();
      if (red[cur] < INF) {
        ans_good[i][red[cur]] = min(ans_good[i][red[cur]], dist[cur] - 1);
      }
      for (auto nxt : tree[cur]) {
        if (!dist[nxt]) {
          bfs.push(nxt);
          dist[nxt] = dist[cur] + 1;
        }
      }
    }
    for (int j = 1; j <= m; j++) {
      ans_good[i][j] = min(ans_good[i][j - 1], ans_good[i][j]);
    }
  }
  for (int i = 1; i <= m; i++) {
    if (q[i].first == 2) {
      printf("%d\n", get_ans(q[i].second, 0, 0, i));
    }
  }
  return 0;
}
