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;
const int MAXN = 100005;
const int MOD = 1000000007;
int N, Q;
vector<int> adj[MAXN], cadj[MAXN];
bool vis[MAXN];
int sze[MAXN];
int cp[MAXN];
int mn[MAXN];
vector<pair<int, int> > dist[MAXN];
int ch[MAXN];
int rt = 0;
void szdfs(int v, int p) {
  sze[v] = 1;
  for (auto i : adj[v]) {
    if (i == p || vis[i]) continue;
    szdfs(i, v);
    sze[v] += sze[i];
  }
}
int cen(int v, int p, int n) {
  for (auto i : adj[v]) {
    if (i == p || vis[i]) continue;
    if (sze[i] > n / 2) return cen(i, v, n);
  }
  return v;
}
void dfs(int v, int p, int c, int d) {
  dist[v].push_back(pair<int, int>(c, d));
  for (auto i : adj[v]) {
    if (i == p || vis[i]) continue;
    dfs(i, v, c, d + 1);
  }
}
int decomp(int v, int p) {
  szdfs(v, -1);
  int n = sze[v];
  v = cen(v, -1, n);
  vis[v] = true;
  if (p != -1) {
    ch[v] = ch[p] + 1;
    cp[v] = p;
  }
  dfs(v, -1, v, 0);
  for (auto i : adj[v]) {
    if (vis[i]) continue;
    int nc = decomp(i, v);
    assert(((int)(dist[nc]).size()) == ch[nc] + 1);
  }
  return v;
}
void colour(int v) {
  int ov = v;
  for (int i = (ch[v]); i >= (0); i--) {
    assert(dist[ov][i].first == v);
    mn[v] = min(mn[v], dist[ov][i].second);
    v = cp[v];
  }
}
int query(int v) {
  int ov = v, ans = INT_MAX;
  for (int i = (ch[v]); i >= (0); i--) {
    assert(dist[ov][i].first == v);
    ans = min(ans, mn[v] + dist[ov][i].second);
    v = cp[v];
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  memset(cp, -1, sizeof cp);
  cin >> N >> Q;
  for (int i = (1); i <= (N - 1); i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  rt = decomp(1, -1);
  for (int i = (1); i <= (N); i++) {
    sort((dist[i]).begin(), (dist[i]).end(),
         [](pair<int, int> a, pair<int, int> b) {
           return ch[a.first] < ch[b.first];
         });
  }
  for (int i = (1); i <= (N); i++) mn[i] = INT_MAX / 2;
  colour(1);
  while (Q--) {
    int op, v;
    cin >> op >> v;
    if (op == 1) {
      colour(v);
    } else {
      cout << query(v) << "\n";
    }
  }
}
