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 long double gr = (1 + sqrt(5)) / 2;
long long n, q;
long long v1, v2, cc, t, pv;
long long csv[100007], lev[100007], par[100007], res[100007];
vector<long long> a[100007];
map<long long, long long> dm[100007];
long long fs(long long v, long long p) {
  csv[v] = 1;
  for (auto to : a[v]) {
    if (lev[to] == 0 && to != p) {
      csv[v] += fs(to, v);
    }
  }
  return csv[v];
}
long long fcentroid(long long v, long long p, long long cs) {
  for (auto to : a[v]) {
    if (lev[to] == 0 && to != p && (2 * csv[to]) > cs) {
      return fcentroid(to, v, cs);
    }
  }
  return v;
}
void fdist(long long v, long long p, long long d) {
  dm[cc][v] = d;
  for (auto to : a[v]) {
    if (lev[to] == 0 && to != p) {
      fdist(to, v, (d + 1));
    }
  }
}
void decomp(long long v, long long p, long long l) {
  long long cs = fs(v, (-1));
  long long c = fcentroid(v, (-1), cs);
  par[c] = p;
  lev[c] = l;
  cc = c;
  fdist(c, (-1), 0);
  for (auto to : a[c]) {
    if (lev[to] == 0) {
      decomp(to, c, (l + 1));
    }
  }
}
long long d(long long v1, long long v2) {
  if (lev[v1] < lev[v2]) return dm[v1][v2];
  return dm[v2][v1];
}
void up(long long v) {
  long long pv = v;
  while (1) {
    res[pv] = min(res[pv], d(v, pv));
    if (par[pv] == (-1)) break;
    pv = par[pv];
  }
}
long long f(long long v) {
  long long pv = v;
  long long ans = 1000000007.0;
  while (1) {
    ans = min(ans, (res[pv] + d(v, pv)));
    if (par[pv] == (-1)) break;
    pv = par[pv];
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  res[1] = 1000000007.0;
  for (int i = 1; i < n; i++) {
    res[i + 1] = 1000000007.0;
    cin >> v1 >> v2;
    a[v1].push_back(v2);
    a[v2].push_back(v1);
  }
  decomp(1, (-1), 1);
  up(1);
  for (int q1 = 1; q1 <= q; q1++) {
    cin >> t >> pv;
    if (t == 1)
      up(pv);
    else
      cout << f(pv) << endl;
  }
}
