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 Int() {
  int x;
  scanf("%d", &x);
  return x;
}
long long Long() {
  long long x;
  scanf("%lld", &x);
  return x;
}
double Double() {
  double x;
  scanf("%lf", &x);
  return x;
}
float Float() {
  float x;
  scanf("%f", &x);
  return x;
}
const int N = 1e5 + 5;
vector<string> split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cout << it->substr((*it)[0] == ' ', it->length()) << " = " << a << "  ";
  err(++it, args...);
}
const int INF = (int)1e9 + 7;
const int Log = 17;
int par[Log + 2][N];
int parF[N];
int level[N];
int child[N];
int Min[N];
set<int> var[N];
int nd;
void dfs(int u, int p = 0) {
  level[u] = level[p] + 1;
  par[0][u] = p;
  for (int i = 1; i <= Log; i++) {
    par[i][u] = par[i - 1][par[i - 1][u]];
  }
  for (auto v : var[u]) {
    if (v != p) dfs(v, u);
  }
}
int LCA(int a, int b) {
  if (level[a] < level[b]) swap(a, b);
  int dis = level[a] - level[b];
  for (int i = Log; i >= 0; i--)
    if (dis & (1 << i)) a = par[i][a];
  for (int i = Log; i >= 0; i--) {
    if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
  }
  return a == b ? a : par[0][a];
}
int dist(int u, int v) { return level[u] + level[v] - (level[LCA(u, v)] << 1); }
void dfs_1(int u, int p) {
  child[u] = 1;
  nd++;
  for (auto v : var[u]) {
    if (v == p) continue;
    dfs_1(v, u);
    child[u] += child[v];
  }
}
int dfs_2(int u, int p) {
  for (auto v : var[u]) {
    if (v != p && child[v] > nd / 2) return dfs_2(v, u);
  }
  return u;
}
void decompose(int u, int p = 0) {
  nd = 0;
  dfs_1(u, u);
  int centroid = dfs_2(u, u);
  parF[centroid] = p;
  for (auto v : var[centroid]) {
    var[v].erase(centroid);
    decompose(v, centroid);
  }
  var[centroid].clear();
}
void update(int u) {
  int i = u;
  while (i) {
    Min[i] = min(Min[i], dist(i, u));
    i = parF[i];
  }
}
int query(int u) {
  int i = u, res = INF;
  while (i) {
    res = min(res, Min[i] + dist(i, u));
    i = parF[i];
  }
  return res;
}
int main() {
  int n = Int() - 1, m = Int();
  for (int i = 0; i < n; i++) {
    int u = Int(), v = Int();
    var[u].insert(v);
    var[v].insert(u);
  }
  fill(Min, Min + N, INF);
  dfs(1);
  decompose(1);
  update(1);
  for (int i = 0; i < m; i++) {
    int type = Int(), u = Int();
    if (type == 1)
      update(u);
    else
      printf("%d\n", query(u));
  }
  return 0;
}
