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("O3", "unroll-loops")
using namespace std;
using pii = pair<long long, long long>;
template <typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using Prior = priority_queue<T>;
const long long INF = 1E18;
const long long mod = 1E9 + 7;
const long long maxn = 1 << 17;
const long long lgmx = 17 + 1;
long long par[maxn][lgmx];
vector<long long> adj[maxn], depth(maxn);
vector<long long> subSize(maxn), cd_par(maxn), dis(maxn, INF);
vector<bool> deleted(maxn, 0);
void dfs(long long now, long long lst, long long dep) {
  par[now][0] = lst == -1 ? now : lst;
  depth[now] = dep;
  for (auto x : adj[now]) {
    if (x == lst) continue;
    dfs(x, now, dep + 1);
  }
}
void lca_init(long long n) {
  for (long long lay = 1; lay < lgmx; ++lay) {
    for (long long i = 1; i <= n; ++i) {
      par[i][lay] = par[par[i][lay - 1]][lay - 1];
    }
  }
}
long long get_lca(long long x, long long y) {
  if (depth[x] < depth[y]) swap(x, y);
  long long diff = depth[x] - depth[y];
  for (long long i = lgmx - 1; i >= 0; --i) {
    if (diff & (1 << i)) x = par[x][i];
  }
  if (x == y) return x;
  for (long long i = lgmx - 1; i >= 0; --i) {
    if (par[x][i] != par[y][i]) {
      x = par[x][i], y = par[y][i];
    }
  }
  return par[x][0];
}
long long get_dis(long long x, long long y) {
  return depth[x] + depth[y] - 2 * depth[get_lca(x, y)];
}
void get_size(long long now, long long lst) {
  subSize[now] = 1;
  for (auto x : adj[now]) {
    if (x == lst or deleted[x]) continue;
    get_size(x, now);
    subSize[now] += subSize[x];
  }
}
long long get_centroid(long long now, long long lst, long long maxSize) {
  for (auto x : adj[now]) {
    if (x == lst or deleted[x]) continue;
    if (subSize[x] > maxSize / 2) {
      return get_centroid(x, now, maxSize);
    }
  }
  return now;
}
void centroid_decomposition(long long now, long long lst) {
  get_size(now, lst);
  long long centroid = get_centroid(now, lst, subSize[now]);
  cd_par[centroid] = lst, deleted[centroid] = 1;
  cerr << "cd_par[" << centroid << "] : " << lst << "\n";
  for (auto x : adj[centroid]) {
    if (x == lst or deleted[x]) continue;
    centroid_decomposition(x, centroid);
  }
}
void update(long long x) {
  long long cp = x;
  while (cp != -1) {
    dis[cp] = min(dis[cp], get_dis(cp, x));
    cp = cd_par[cp];
  }
}
long long query(long long x, long long ans = INF) {
  long long cp = x;
  while (cp != -1) {
    ans = min(ans, dis[cp] + get_dis(cp, x));
    cp = cd_par[cp];
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, m, u, v, op, idx;
  cin >> n >> m;
  for (long long i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, -1, 0);
  lca_init(n);
  centroid_decomposition(1, -1);
  update(1);
  while (m--) {
    cin >> op >> idx;
    if (op == 1)
      update(idx);
    else
      cout << query(idx) << "\n";
  }
  return 0;
}
