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;
int n, m;
set<int> g[100010];
int sub[100010];
int P[100010];
int dp[21][100010];
int d[100010];
void add(int p, int q) {
  g[q].insert(p);
  g[p].insert(q);
}
void remove(int p, int q) {
  g[p].erase(q);
  g[q].erase(p);
}
void dfs(int x, int pa) {
  sub[x] = 1;
  for (auto i : g[x]) {
    if (i == pa) continue;
    dfs(i, x);
    sub[x] += sub[i];
  }
}
void get(int x, int pa) {
  dp[0][x] = pa;
  d[x] = 1 + d[pa];
  for (int i : g[x]) {
    if (i == pa) continue;
    get(i, x);
  }
}
int find_centroid(int x, int pa, int range) {
  for (auto i : g[x]) {
    if (i == pa) continue;
    if (sub[i] > range) {
      return find_centroid(i, x, range);
    }
  }
  return x;
}
void build_tree(int x, int pa) {
  dfs(x, 0);
  int c = find_centroid(x, 0, sub[x] / 2);
  P[c] = pa;
  vector<int> v;
  copy(g[c].begin(), g[c].end(), back_inserter(v));
  for (auto i : v) {
    remove(c, i);
    build_tree(i, c);
  }
}
int ans[100010];
int lca(int u, int v) {
  if (d[u] > d[v]) swap(u, v);
  for (int i = 20; i >= 0; i--) {
    if (d[v] - (1 << i) >= d[u]) {
      v = dp[i][v];
    }
  }
  if (u == v) return v;
  for (int i = 20; i >= 0; i--) {
    if (dp[i][u] != dp[i][v] and dp[i][u] and dp[i][v]) {
      u = dp[i][u];
      v = dp[i][v];
    }
  }
  return dp[0][u];
}
inline int dist(int p, int q) { return d[p] + d[q] - (2 * d[lca(p, q)]); }
void update(int x) {
  int k = x;
  while (x != 0) {
    ans[x] = min(ans[x], dist(x, k));
    x = P[x];
  }
}
int query(int x) {
  int res = 10000000;
  int k = x;
  while (x != 0) {
    res = min(res, dist(x, k) + ans[x]);
    x = P[x];
  }
  return res;
}
int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int p, q;
    cin >> p >> q;
    add(p, q);
  }
  get(1, 0);
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
  }
  memset(ans, 63, sizeof ans);
  build_tree(1, 0);
  update(1);
  for (int i = 1; i <= m; i++) {
    int t, x;
    cin >> t >> x;
    if (t == 1)
      update(x);
    else
      cout << query(x) << endl;
  }
  return 0;
}
