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 maxn = 2e5 + 11;
const int MAXN = 1e5 + 5;
const int LG = 20;
const int INF = 1e9;
using ll = long long int;
using ull = unsigned long long int;
const ll MOD2 = 998244353;
const ll MOD1 = 1e9 + 7LL;
vector<int> g[MAXN], cg[MAXN];
vector<int> cpar(MAXN);
vector<int> ans(MAXN);
int n, m;
struct CDMP {
  vector<bool> dead;
  vector<int> par;
  int oneCentroid(int root) {
    static vector<int> sub(MAXN);
    function<void(int, int)> dfs = [&](int u, int p) {
      sub[u] = 1;
      for (int v : g[u]) {
        if (v == p || dead[v]) continue;
        dfs(v, u);
        sub[u] += sub[v];
      }
    };
    dfs(root, -1);
    int N = sub[root];
    function<int(int, int)> findcenter = [&](int u, int p) {
      for (int v : g[u]) {
        if (v == p || dead[v]) continue;
        if (2 * sub[v] > N) return findcenter(v, u);
      }
      return u;
    };
    return findcenter(root, -1);
  }
  void traverse(int u, int p, int d = 0) {
    par[u] = p;
    for (int v : cg[u]) {
      if (v != p) {
        traverse(v, u, d + 1);
      }
    }
  }
  vector<int> &decomposeTree() {
    par = vector<int>(MAXN, -1);
    dead = vector<bool>(MAXN, false);
    function<int(int)> rec = [&](int u) {
      int c = oneCentroid(u);
      dead[c] = true;
      for (int v : g[c])
        if (!dead[v]) {
          int cv = rec(v);
          cg[c].push_back(cv);
          cg[cv].push_back(c);
        }
      return c;
    };
    int r = rec(1);
    traverse(r, -1);
    return par;
  }
} cdmp;
struct computeLCA {
  int level[MAXN];
  int par[MAXN][LG];
  int findlca(int u, int v) {
    if (level[u] < level[v]) swap(u, v);
    int lg = 0;
    for (; (1 << lg) <= level[u]; ++lg)
      ;
    --lg;
    for (int i = lg; i >= 0; --i)
      if (level[u] - (1 << i) >= level[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = lg; i >= 0; --i)
      if (par[u][i] != -1 && par[u][i] != par[v][i])
        u = par[u][i], v = par[v][i];
    return par[u][0];
  }
  int dist(int u, int v) {
    return level[u] + level[v] - 2 * level[findlca(u, v)];
  }
  void dfs(int u, int p) {
    level[u] = 1 + level[p];
    par[u][0] = p;
    for (int v : g[u])
      if (v != p) {
        dfs(v, u);
      }
  }
  void build() {
    level[1] = 0;
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j < LG; ++j) par[i][j] = -1;
    dfs(1, 1);
    for (int l = 1; l < LG; ++l)
      for (int i = 1; i <= n; ++i)
        if (par[i][l - 1] != -1) {
          par[i][l] = par[par[i][l - 1]][l - 1];
        }
  }
} lca;
void update(int x) {
  int node = x;
  while (node > 0) {
    ans[node] = min(ans[node], lca.dist(node, x));
    node = cpar[node];
  }
}
int query(int x) {
  int node = x;
  int ret = INF;
  while (node > 0) {
    ret = min(ret, lca.dist(node, x) + ans[node]);
    node = cpar[node];
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d", &u);
    scanf("%d", &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i <= n; ++i) ans[i] = INF;
  cpar = cdmp.decomposeTree();
  lca.build();
  update(1);
  while (m--) {
    int t, x;
    scanf("%d", &t);
    scanf("%d", &x);
    if (t == 1) {
      update(x);
    } else {
      printf("%d", query(x));
      printf("\n");
    }
  }
  return 0;
}
