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;
long long int uarr[100005], varr[100005];
vector<long long int> edge[100005];
long long int par_centroid[100005];
long long int par[100005];
long long int sub_size[100005];
long long int level_centroid[100005];
long long int level[100005];
long long int ans[100005];
long long int dp[30][100005];
long long int deleted[100005];
long long int lca_dp[100005][30];
long long int adjacent_edge(long long int e, long long int u) {
  return uarr[e] ^ varr[e] ^ u;
}
void pre_lca(long long int n) {
  long long int i, j;
  for (j = 1; (1 << j) < n; j++) {
    for (i = 1; i <= n; i++) {
      lca_dp[i][j] = -1;
    }
  }
  for (i = 1; i <= n; i++) {
    lca_dp[i][0] = par[i];
  }
  for (j = 1; (1 << j) < n; j++) {
    for (i = 1; i <= n; i++) {
      if (lca_dp[i][j - 1] != -1) {
        lca_dp[i][j] = lca_dp[lca_dp[i][j - 1]][j - 1];
      }
    }
  }
}
long long int lca_query(long long int u, long long int v) {
  long long int i, tmp, log1;
  if (level[u] < level[v]) {
    tmp = u;
    u = v;
    v = tmp;
  }
  log1 = 0;
  for (log1 = 1; (1 << log1) <= level[u]; log1++)
    ;
  log1--;
  for (i = log1; i >= 0; i--) {
    if (level[u] - (1 << i) >= level[v]) {
      u = lca_dp[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (i = log1; i >= 0; i--) {
    if (lca_dp[u][i] != -1 && lca_dp[u][i] != lca_dp[v][i]) {
      u = lca_dp[u][i];
      v = lca_dp[v][i];
    }
  }
  return par[u];
}
void dfs_pre_lca(long long int u, long long int p, long long int lev) {
  level[u] = lev;
  par[u] = p;
  for (auto e : edge[u]) {
    long long int v = adjacent_edge(e, u);
    if (v == p) continue;
    dfs_pre_lca(v, u, lev + 1);
  }
}
void dfs(long long int u, long long int p) {
  sub_size[u] = 1;
  for (auto e : edge[u]) {
    long long int v = adjacent_edge(e, u);
    if (deleted[e] || v == p) continue;
    dfs(v, u);
    sub_size[u] += sub_size[v];
  }
}
long long int find_centroid(long long int u, long long int p, long long int n) {
  for (auto e : edge[u]) {
    long long int v = adjacent_edge(e, u);
    if (!deleted[e] && v != p && sub_size[v] > n / 2) {
      return find_centroid(v, u, n);
    }
  }
  return u;
}
void delete_edges(long long int centroid) {
  for (auto e : edge[centroid]) {
    deleted[e] = 1;
  }
}
void dfs2(long long int u, long long int p, long long int lvl) {
  sub_size[u] = 1;
  for (auto e : edge[u]) {
    long long int v = adjacent_edge(e, u);
    if (deleted[e] || v == p) continue;
    dfs2(v, u, lvl + 1);
  }
}
void add_edge_in_centroid_tree(long long int child, long long int parent) {
  par_centroid[child] = parent;
  level_centroid[child] = (parent == -1 ? 0 : level_centroid[parent]) + 1;
}
void decompose(long long int u, long long int p) {
  dfs(u, p);
  long long int centroid = find_centroid(u, p, sub_size[u]);
  add_edge_in_centroid_tree(centroid, p);
  dfs2(centroid, p, level_centroid[centroid]);
  for (auto e : edge[centroid]) {
    if (deleted[e]) continue;
    deleted[e] = 1;
    long long int v = adjacent_edge(e, centroid);
    decompose(v, centroid);
  }
}
long long int dist_orig(long long int u, long long int v) {
  long long int lca = lca_query(u, v);
  return level[u] + level[v] - 2 * level[lca];
}
int main() {
  long long int n, m, u, v, i, ty;
  scanf("%lld", &n);
  scanf("%lld", &m);
  for (i = 1; i <= n - 1; i++) {
    scanf("%lld", &u);
    scanf("%lld", &v);
    uarr[i] = u;
    varr[i] = v;
    edge[u].push_back(i);
    edge[v].push_back(i);
  }
  dfs_pre_lca(1, -1, 1);
  pre_lca(n);
  decompose(1, -1);
  ans[1] = 0;
  for (i = 2; i <= n; i++) {
    ans[i] = level[i] - level[1];
  }
  while (m--) {
    scanf("%lld", &ty);
    scanf("%lld", &u);
    if (ty == 1) {
      ans[u] = 0;
      v = u;
      while (v != -1) {
        ans[v] = min(ans[v], dist_orig(u, v));
        v = par_centroid[v];
      }
    } else {
      long long int mn = 1e10;
      v = u;
      while (v != -1) {
        mn = min(mn, ans[v] + dist_orig(u, v));
        v = par_centroid[v];
      }
      printf("%lld", mn);
      ;
      printf("\n");
      ;
    }
  }
  return 0;
}
