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>
const long long md = 998244353;
const int Inf = 1e9;
const long long Inf64 = 1e18;
const long long MaxN = 1e5 + 10;
const long long LogN = 20;
const long long MaxM = 1e10;
const long double eps = 1e-7;
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
const long long ddx[4] = {1, 1, -1, -1};
const long long ddy[4] = {1, -1, 1, -1};
const long double Pi = acos(-1);
using namespace std;
inline long long Mod(long long &a, long long m = md) {
  while (a > m) a -= m;
  return a;
}
inline long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
}
inline long long gcdex(long long a, long long mod = md) {
  long long g = mod, r = a, x = 0, y = 1;
  while (r != 0) {
    long long q = g / r;
    g %= r;
    swap(g, r);
    x -= q * y;
    swap(x, y);
  }
  return x < 0 ? x + mod : x;
}
inline long long binpow(long long a, long long n, long long m = md) {
  long long res = 1;
  while (n) {
    if (n & 1) {
      res *= a;
      res %= m;
    }
    a *= a;
    a %= m;
    n >>= 1;
  }
  return res % md;
}
vector<long long> Gr[MaxN];
long long Mt[MaxN];
long long D[MaxN];
long long N, M;
long long up[MaxN][LogN];
long long tin[MaxN], tout[MaxN];
long long T = 1;
long long H[MaxN];
void dfs(long long v, long long h, long long p = 1) {
  tin[v] = T++;
  up[v][0] = p;
  H[v] = h;
  for (int i = 1; i < LogN; i++) {
    up[v][i] = up[up[v][i - 1]][i - 1];
  }
  for (long long to : Gr[v]) {
    if (to == p) continue;
    dfs(to, h + 1, v);
  }
  tout[v] = T++;
}
bool upper(long long a, long long b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}
long long Dist(long long v, long long to) {
  long long lca = v;
  if (upper(v, to))
    lca = v;
  else if (upper(to, v))
    lca = to;
  else {
    for (long long l = LogN - 1; l >= 0; l--) {
      if (!upper(up[lca][l], to)) {
        lca = up[lca][l];
      }
    }
    lca = up[lca][0];
  }
  long long Ans = H[v] - H[lca] + H[to] - H[lca];
  return Ans;
}
void bfs() {
  fill(D, D + N + 1, Inf);
  queue<pair<long long, long long> > BFS;
  BFS.push({1, 0});
  D[1] = 0;
  while (!BFS.empty()) {
    pair<long long, long long> a = BFS.front();
    BFS.pop();
    long long v = a.first;
    long long d = a.second;
    for (long long to : Gr[v]) {
      if (D[to] > d + 1) {
        D[to] = d + 1;
        if (Mt[to] == 1) {
          D[to] = 0;
          BFS.push({to, 0});
        } else {
          D[to] = d + 1;
          BFS.push({to, d + 1});
        }
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> M;
  for (int i = 0; i < N - 1; i++) {
    long long a, b;
    cin >> a >> b;
    Gr[a].push_back(b);
    Gr[b].push_back(a);
  }
  dfs(1, 1);
  Mt[0] = 1;
  long long w = sqrt(M);
  set<long long> St;
  for (int i = 0; i < M; i++) {
    if (i % w == 0) {
      bfs();
      St.clear();
    }
    long long a, b;
    cin >> a >> b;
    if (a == 2) {
      long long Ans = D[b];
      for (long long to : St) {
        Ans = min(Ans, Dist(to, b));
      }
      cout << Ans << '\n';
    } else {
      Mt[b] = 1;
      St.insert(b);
    }
  }
  cerr << '\n'
       << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec"
       << '\n';
  return 0;
}
