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 inf = 1e9 + 5;
const long long infll = 1e18 + 5ll;
const long double eps = 1e-9;
const int maxn = 1e5 + 100;
const long long maxlog = 21;
const int P = 97;
const int mod = 1e9 + 9;
int n, m, lvl[maxn], up[maxlog][maxn], sub[maxn], par[maxn], ans[maxn];
std::vector<int> g[maxn];
bool ban[maxn];
void dfs1(int v = 1, int pr = 0) {
  lvl[v] = lvl[pr] + 1;
  up[0][v] = pr;
  for (int i = 1; i < 20; ++i) up[i][v] = up[i - 1][up[i - 1][v]];
  for (auto to : g[v])
    if (pr != to) {
      dfs1(to, v);
    }
}
int nn;
void dfs2(int v, int pr) {
  sub[v] = 1;
  ++nn;
  for (auto to : g[v]) {
    if (to != pr && !ban[to]) {
      dfs2(to, v);
      sub[v] += sub[to];
    }
  }
}
int getCentroid(int v, int pr) {
  for (auto to : g[v]) {
    if (to != pr && !ban[to] && sub[to] * 2 > nn) {
      return getCentroid(to, v);
    }
  }
  return v;
}
void decompose(int v, int pr) {
  nn = 0;
  dfs2(v, pr);
  int centroid = getCentroid(v, pr);
  par[centroid] = pr;
  ban[centroid] = 1;
  for (auto to : g[centroid]) {
    if (to == pr || ban[to]) continue;
    decompose(to, centroid);
  }
}
int lca(int a, int b) {
  if (lvl[a] > lvl[b]) swap(a, b);
  int d = lvl[b] - lvl[a];
  for (int i = 0; i < maxlog; ++i)
    if (d & (1 << i)) b = up[i][b];
  if (a == b) return b;
  for (int i = maxlog - 1; i >= 0; --i)
    if (up[i][a] != up[i][b]) a = up[i][a], b = up[i][b];
  return up[0][a];
}
int dist(int u, int v) { return lvl[u] + lvl[v] - 2 * lvl[lca(u, v)]; }
void upd(int v) {
  int x = v;
  while (x != 0) {
    ans[x] = min(ans[x], dist(x, v));
    x = par[x];
  }
}
int query(int v) {
  int x = v, res = inf;
  while (x != 0) {
    res = min(res, ans[x] + dist(x, v));
    x = par[x];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
  if (fopen("sorting"
            ".in",
            "r"))
    freopen(
        "sorting"
        ".in",
        "r", stdin),
        freopen(
            "sorting"
            ".out",
            "w", stdout);
  ;
  cin >> n >> m;
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs1();
  decompose(1, 0);
  memset(ans, inf, sizeof ans);
  upd(1);
  for (int i = 1, t, v; i <= m; ++i) {
    cin >> t >> v;
    if (t == 1) {
      upd(v);
    } else {
      cout << query(v) << '\n';
    }
  }
  return 0;
}
