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>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
const long long mod = 998244353;
const int inf = INT_MAX;
struct item {
  long long n;
  item(int x = inf) : n(x) {}
  item operator+(const item &oth) {
    item r;
    r.n = min(n, oth.n);
    return r;
  }
};
template <class node>
struct segtree {
  int n;
  vector<node> st;
  void init(int _n) {
    n = _n;
    st.assign(2 * n, node());
  }
  inline int le(int x) { return 2 * x + 1; }
  inline int ri(int x) { return 2 * x + 2; }
  void build(vector<int> &a) {
    init(a.size());
    for (int i = n; i < 2 * n; i++) st[i] = a[i - n];
    for (int i = n - 1; i > 0; i--) st[i] = st[i << 1] + st[i << 1 | 1];
  }
  void set(int i, int x) {
    i += n;
    for (st[i] = st[i] + x; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
  }
  node query(int l, int r) {
    node anl, anr;
    r++;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) anl = anl + st[l++];
      if (r & 1) anr = st[--r] + anr;
    }
    return anl + anr;
  }
};
template <class node>
struct hld {
  int n, t;
  vector<int> tot, up, tin, tout, down, dep, par;
  vector<vector<int>> adj;
  segtree<node> stup, stdown;
  void init(int _n) {
    n = _n;
    t = 0;
    stup.init(n);
    stdown.init(n);
    tot.assign(n, 0);
    up.assign(n, 0);
    tin.assign(n, 0);
    tout.assign(n, 0);
    down.assign(n, 0);
    dep.assign(n, 0);
    par.assign(n, 0);
    adj.assign(n, vector<int>(0));
  }
  void dfs_tot(int v = 0, int p = -1) {
    tot[v] = 1;
    par[v] = p;
    for (auto &u : adj[v]) {
      if (u == p) continue;
      dep[u] = dep[v] + 1;
      dfs_tot(u, v);
      tot[v] += tot[u];
      if (adj[v][0] == p || tot[u] > tot[adj[v][0]]) {
        swap(u, adj[v][0]);
      }
    }
  }
  void dfs_hld(int v = 0, int p = -1) {
    tin[v] = t++;
    for (auto u : adj[v]) {
      if (u == p) continue;
      up[u] = (u == adj[v][0] ? up[v] : u);
      down[up[u]] = u;
      dfs_hld(u, v);
    }
    tout[v] = t;
  }
  void setup(int i, int x) { stup.set(i, x); }
  int queryup(int l, int r) { return (stup.query(l, r)).n; }
  void setdown(int i, int x) { stdown.set(i, x); }
  int querydown(int l, int r) { return (stdown.query(l, r)).n; }
  void put(int i, int dis) {
    setup(tin[i], dis + dep[i] - dep[up[i]]);
    setdown(tin[i], dis + dep[down[up[i]]] - dep[i]);
  }
  void put(int i) {
    int dis = 0;
    while (true) {
      put(i, dis);
      int p = par[up[i]];
      if (p == -1) break;
      dis += dep[i] - dep[p];
      i = p;
    }
  }
  int query(int i) {
    int x = inf, dis = 0;
    while (true) {
      x = min({x - dis,
               queryup(tin[i], tin[down[up[i]]]) - (dep[i] - dep[up[i]]),
               querydown(tin[up[i]], tin[i]) - (dep[down[up[i]]] - dep[i])});
      x += dis;
      int p = par[up[i]];
      if (p == -1) break;
      dis += dep[i] - dep[p];
      i = p;
    }
    return x;
  }
};
int n, m, a, b, tag, v;
void solve() {
  cin >> n >> m;
  hld<item> hl;
  hl.init(n);
  for (int i = (int)1; i != (int)n; i = i + 1) {
    cin >> a >> b;
    a--;
    b--;
    hl.adj[a].push_back(b);
    hl.adj[b].push_back(a);
  }
  hl.dfs_tot();
  hl.dfs_hld();
  hl.put(0, 0);
  while (m--) {
    cin >> tag >> v;
    v--;
    if (tag == 1) {
      hl.put(v);
    } else {
      cout << hl.query(v) << '\n';
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}
