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>
inline void maxa(T& a, T b) {
  a = max(a, b);
}
template <typename T>
inline void mina(T& a, T b) {
  a = min(a, b);
}
const int mxN = 2e5 + 5;
int n, q, a, b, par[mxN], ans[mxN], dist[mxN][22], st[4 * mxN], ht[mxN], T[mxN],
    sub[mxN];
set<int> graph[mxN];
vector<int> vis;
int minh(int x, int y) { return ht[x] < ht[y] ? x : y; }
int build_st(int v, int l, int r) {
  if (l == r) {
    return st[v] = vis[l];
  }
  int m = (l + r) >> 1;
  return st[v] = minh(build_st(v << 1, l, m), build_st(v << 1 | 1, m + 1, r));
}
int query_st(int v, int l, int r, int lq, int rq) {
  if (lq > rq) {
    return 0;
  }
  if (l >= lq && r <= rq) {
    return st[v];
  }
  int m = (l + r) >> 1;
  return minh(query_st(v << 1, l, m, lq, min(rq, m)),
              query_st(v << 1 | 1, m + 1, r, max(lq, m + 1), rq));
}
void pre() {
  for (int i = 1; i <= n; i++) {
    int j = i;
    int cnt = 0;
    while (j != par[j]) {
      j = par[j];
      cnt++;
      int v1 = T[i];
      int v2 = T[j];
      if (v1 > v2) {
        swap(v1, v2);
      }
      int lca = query_st(1, 1, vis.size() - 1, v1, v2);
      dist[i][cnt] = ht[i] + ht[j] - 2 * ht[lca];
    }
  }
}
void euler(int at, int p, int h) {
  T[at] = vis.size();
  vis.push_back(at);
  ht[at] = h;
  for (int i : graph[at]) {
    if (i == p) continue;
    euler(i, at, h + 1);
    vis.push_back(at);
  }
}
int dfs(int at, int p) {
  int ret = 1;
  for (int i : graph[at]) {
    if (i == p) continue;
    ret += dfs(i, at);
  }
  return sub[at] = ret;
}
int centroid(int at, int p, int s) {
  for (int i : graph[at]) {
    if (i == p) continue;
    if (sub[i] * 2 >= s) return centroid(i, at, s);
  }
  return at;
}
void build(int at, int p) {
  int s = dfs(at, p);
  int cent = centroid(at, p, s);
  if (p == -1) {
    p = cent;
  }
  par[cent] = p;
  for (auto u : graph[cent]) {
    graph[u].erase(cent);
    build(u, cent);
  }
}
void update(int x) {
  ans[x] = 0;
  int cnt = 0;
  int y = x;
  while (y != par[y]) {
    y = par[y];
    cnt++;
    mina(ans[y], dist[x][cnt]);
  }
}
int query(int x) {
  int ret = ans[x];
  int y = x;
  int cnt = 0;
  while (y != par[y]) {
    y = par[y];
    cnt++;
    mina(ret, ans[y] + dist[x][cnt]);
  }
  return ret;
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) ans[i] = 1e9;
  for (int i = 0; i < n - 1; i++) {
    cin >> a >> b;
    graph[a].insert(b);
    graph[b].insert(a);
  }
  ht[0] = 1e9;
  vis.push_back(0);
  euler(1, -1, 0);
  build_st(1, 1, vis.size() - 1);
  build(1, -1);
  pre();
  update(1);
  while (q--) {
    cin >> a >> b;
    if (a == 1)
      update(b);
    else
      cout << query(b) << "\n";
  }
}
