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;
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& it : v) is >> it;
  return is;
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> second) {
  os << "{ ";
  for (auto s : second) os << s << " ";
  return os << "}";
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " |";
  __f(comma + 1, args...);
}
struct pairHash {
  inline size_t operator()(const pair<int, int>& p) const {
    return p.first * 31 + p.second;
  }
};
const int N = 1e5, logN = 40;
unordered_set<int> adj[N];
vector<int> size(N);
vector<int> papa(N), level(N);
vector<vector<int> > dist(N, vector<int>(logN));
vector<int> ans(N, 1e9);
vector<bool> isWhite(N);
int getSize(int node, int par = -1) {
  size[node] = 1;
  for (auto child : adj[node]) {
    if (child == par) continue;
    size[node] += getSize(child, node);
  }
  return size[node];
}
int findCentroid(int node, int par, int& sz) {
  for (auto child : adj[node]) {
    if (child == par) continue;
    if (size[child] > sz / 2) {
      return findCentroid(child, node, sz);
    }
  }
  return node;
}
void compute(int node, int par, int& centlvl) {
  for (auto child : adj[node]) {
    if (child == par) continue;
    dist[child][centlvl] = dist[node][centlvl] + 1;
    compute(child, node, centlvl);
  }
}
void decompose(int root = 0, int par = -1) {
  int sz = getSize(root);
  int centroid = findCentroid(root, -1, sz);
  papa[centroid] = par;
  if (par != -1) {
    level[centroid] = level[par] + 1;
  }
  compute(centroid, -1, level[centroid]);
  for (auto newRoot : adj[centroid]) {
    adj[newRoot].erase(centroid);
    decompose(newRoot, centroid);
  }
  adj[centroid].clear();
}
void solve() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].insert(v);
    adj[v].insert(u);
  }
  decompose();
  int pu = 0;
  while (pu != -1) {
    ans[pu] = min(ans[pu], (dist[0][level[pu]]));
    pu = papa[pu];
  }
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int u;
      cin >> u;
      u--;
      int pu = u;
      while (pu != -1) {
        ans[pu] = min(ans[pu], (dist[u][level[pu]]));
        pu = papa[pu];
      }
    } else {
      int u;
      cin >> u;
      u--;
      int ans2 = 1e9, pu = u;
      while (pu != -1) {
        ans2 = min(ans2, (ans[pu] + dist[u][level[pu]]));
        pu = papa[pu];
      }
      if (ans2 >= 1e9) ans2 = -1;
      cout << ans2 << '\n';
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
