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 long INF = 1e9;
long long n, m;
vector<long long> ed[100005];
long long pre[100005], h[100005];
long long sz[100005];
long long ans[100005];
bool isCen[100005];
long long par[100005][21];
void dfs(long long u, long long p) {
  for (long long i = 0; i < ed[u].size(); i++) {
    long long v = ed[u][i];
    if (v == p) continue;
    h[v] = h[u] + 1;
    par[v][0] = u;
    dfs(v, u);
  }
}
long long LCA(long long u, long long v) {
  if (h[u] > h[v]) swap(u, v);
  long long diff = h[v] - h[u];
  for (long long i = 20; i >= 0; i--)
    if (diff & (1 << i)) v = par[v][i];
  if (v == u) return u;
  for (long long i = 20; i >= 0; i--)
    if (par[v][i] != -1 && par[u][i] != -1 && par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  return par[u][0];
}
long long dist(long long u, long long v) {
  return h[u] + h[v] - 2 * h[LCA(u, v)];
}
void Size(long long u, long long p) {
  sz[u] = 1;
  for (long long i = 0; i < ed[u].size(); i++) {
    long long v = ed[u][i];
    if (v == p || isCen[v]) continue;
    Size(v, u);
    sz[u] += sz[v];
  }
}
long long Find(long long u, long long p, long long lim) {
  for (long long i = 0; i < ed[u].size(); i++) {
    long long v = ed[u][i];
    if (v != p && !isCen[v] && sz[v] > lim) return Find(v, u, lim);
  }
  return u;
}
void CD(long long u, long long p) {
  Size(u, 0);
  long long c = Find(u, 0, sz[u] / 2);
  isCen[c] = 1;
  pre[c] = p;
  for (long long i = 0; i < ed[c].size(); i++) {
    long long v = ed[c][i];
    if (!isCen[v]) CD(v, c);
  }
}
void upd(long long u) {
  for (long long v = u; v; v = pre[v]) ans[v] = min(ans[v], dist(v, u));
}
long long calc(long long u) {
  long long mn = INF;
  for (long long v = u; v; v = pre[v]) mn = min(mn, dist(v, u) + ans[v]);
  return mn;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(par, -1, sizeof(par));
  cin >> n >> m;
  for (long long i = 0; i <= n; i++) ans[i] = INF;
  for (long long i = 1; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    ed[a].push_back(b);
    ed[b].push_back(a);
  }
  dfs(1, 0);
  for (long long j = 1; j <= 20; j++)
    for (long long i = 1; i <= n; i++)
      if (par[i][j - 1] != -1)
        if (par[par[i][j - 1]][j - 1] != -1)
          par[i][j] = par[par[i][j - 1]][j - 1];
  CD(1, 0);
  upd(1);
  while (m--) {
    long long t, u;
    cin >> t >> u;
    if (t == 1)
      upd(u);
    else
      cout << calc(u) << "\n";
  }
}
