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> mat[100010];
vector<pair<int, int> > paInfo[100010];
int lev[100010], pa, cen, sub[100010], tr_sz, dis[100010];
int close[100010];
void col_info(int p, int baap) {
  if (cen) paInfo[p].push_back({cen, dis[p]});
  sub[p] = 1;
  for (auto x : mat[p]) {
    if (lev[pa] < lev[x]) pa = x;
    if (x == baap || lev[x]) continue;
    dis[x] = dis[p] + 1;
    col_info(x, p);
    sub[p] += sub[x];
  }
}
int centroid(int p, int baap) {
  if ((sub[p] << 1) <= tr_sz) return baap;
  for (auto x : mat[p])
    if ((sub[x] << 1) > tr_sz && !lev[x] && x != baap) return centroid(x, p);
  return p;
}
void update(int p) {
  for (auto x : paInfo[p])
    close[x.first] =
        close[x.first] == -1 ? x.second : min(close[x.first], x.second);
}
int query(int p) {
  int ret = 100010;
  for (auto x : paInfo[p])
    if (close[x.first] != -1) ret = min(close[x.first] + x.second, ret);
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  memset(close, -1, sizeof(close));
  int n, u, v, ty, p, m;
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    mat[u].push_back(v);
    mat[v].push_back(u);
  }
  for (int l = 1; l <= 18; l++)
    for (int i = 1; i <= n; i++) {
      if (lev[i]) continue;
      pa = 0;
      col_info(i, i);
      tr_sz = sub[i];
      cen = centroid(i, i);
      dis[cen] = 0;
      col_info(cen, cen);
      lev[cen] = lev[pa] + 1;
      cen = 0;
    }
  update(1);
  for (int i = 1; i <= m; i++) {
    cin >> ty >> p;
    if (ty == 1)
      update(p);
    else
      cout << query(p) << endl;
  }
  return 0;
}
